【Day 13 】2024-04-20 - 104. 二叉树的最大深度

[azl397985856]

104. 二叉树的最大深度

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/maximum-depth-of-binary-tree

前置知识

• 递归

  题目描述

  
  给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例： 给定二叉树 [3,9,20,null,null,15,7]，

3

/ \ 9 20 / \ 15 7 返回它的最大深度 3 。

[zhiyuanpeng]

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        max_depth = [-1]
        self.dfs(root, 0, max_depth)
        return max_depth[0]

    def dfs(self, root, current_depth, max_depth):
        if not root:
            return
        current_depth += 1
        max_depth[0] = max(max_depth[0], current_depth)
        self.dfs(root.left, current_depth, max_depth)
        self.dfs(root.right, current_depth, max_depth)   

time O(N) space O(logN)

[Dtjk]

class Solution { public: int maxDepth(TreeNode* root) { if(root==nullptr){ return 0 ; } return max(maxDepth(root->left)+1,maxDepth(root->right)+1); } };

[lxy1108]

思路

采用层次遍历，每次循环遍历该层节点并将该层节点的子节点加入队列中，循环过程中记录层数，即为最大深度

python3代码

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        queue = collections.deque([root])
        height = 0
        while queue:
            height+=1
            q_tmp = []
            for node in queue:
                if node.left:
                    q_tmp.append(node.left)
                if node.right:
                    q_tmp.append(node.right)
            queue=q_tmp
        return height

复杂度分析

时间复杂度O(N)，因为需要遍历树 空间复杂度取决于树的结构，最坏情况为O(N)

[CathyShang]

思路：

• 后续遍历二叉树
• 分别遍历左子树，右子树，有叶节点就加1，进行递归。
• 递归结束 当遍历到根节点 return 1；
• 递归中，return max(a.计算左子树深度 maxD(root->left) b.计算左子树深度 maxD(root->right) )+1。

代码：

class Solution {
public:
    int maxD(TreeNode* root){
        if(!root){return 0;}
        // std::cout << root->val<< endl;
        // maxD(root->left);
        // maxD(root->right); // 超时
        return max(maxD(root->left),maxD(root->right))+1;

    }
    int maxDepth(TreeNode* root) {
        int res = -1;
        res = maxD(root);
        return res;
    }
};

复杂度：

• 时间 $O(N)$ 遍历所有节点
• 空间 $O(N)$

[Junru281]

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        # 不用check的原因是,我们已经在leaf node的时候return 0了
        left_depth = self.maxDepth(root.left)
        right_depth = self.maxDepth(root.right)
        return max(left_depth, right_depth) + 1

[GReyQT]

题解思路：

（1）分解子问题：每一次都是计算当前子树的最大深度 （2）子问题推导递推公式： leftDepth = maxDepth(root->left); rightDepth = maxDepth(root->right); (leftDepth, rightDepth) + 1； （2）判断递归终止条件，当节点为空时； 代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        // 递归的终止条件：当节点为空时，返回深度为 0
        if (root == NULL) {
            return 0;
        } else {
            // 递归地计算左右子树的最大深度
            int leftDepth = maxDepth(root->left);
            int rightDepth = maxDepth(root->right);
            // 返回左右子树最大深度中的较大值加上 1（当前节点的深度）
            return max(leftDepth, rightDepth) + 1;
        }
    }
};

复杂度分析：

• 时间复杂度：取决于二叉树节点的个数n，因此时间的复杂度为O(n)
• 空间复杂度：取决于二叉树的最大深度maxDepth，每一层递归调用都会使用一定的堆栈空间，因此空间复杂度为 O(maxDepth)

[YANGLimbo]

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root == nullptr){
            return 0;
        }
        int leftDepth = root->left == nullptr ? 0 : maxDepth(root->left);
        int rightDepth = root->right == nullptr ? 0 : maxDepth(root->right);
        return max(leftDepth,rightDepth) +1;
    }
};

[atom-set]

代码

var maxDepth = function (root) {
  if (root === null) {
    return 0;
  }

  return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
};

复杂度分析

• 时间复杂度: O(N)
• 空间复杂度: O(H), H 是树的高度

[wwz223]

/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    let i = 0
    const getDepth = (node,index)=>{
        if(!root || root.val === null) return index
        index ++ 
        let left  = index
        let right = index
        if(node.left) {
            left = getDepth(node.left,index)
        }
        if (node.right){
           right = getDepth(node.right,index)
        }
        return Math.max(left,right) 
    }

    return getDepth(root, 0)
};

复杂度分析

• 时间复杂度：O(N)
• 空间复杂度：O(N)

[qinmengx]

思路 : 递归的方法, 假设最底层有一排空节点, 倒推出开始有实体数字的节点为1 ,逐层倒推, 逐层加1 , 最终求得深度

type TreeNode struct {

Val   int

Left  *TreeNode

Right *TreeNode

}

func maxDepth(root *TreeNode) int {

if root == nil {
    return 0
}

return Max(maxDepth(root.Left), maxDepth(root.Right)) + 1

}

func Max(a, b int) int {

if a > b {
    return a
} else {
    return b
}

}