二叉树的最大深度 | 秋招知识库

视频讲解

注：本文的「自底向上」和「自顶向下」，关注的都是深度信息如何在父子之间传递。

方法一：自底向上

Python 解法1C++ 解法1

python

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        l_depth = self.maxDepth(root.left)
        r_depth = self.maxDepth(root.right)
        return max(l_depth, r_depth) + 1

cpp

// C++ 版待补充

C++ 解法2

cpp

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

复杂度分析

时间复杂度： $O (n)$ ，其中 $n$ 为二叉树的节点个数。
空间复杂度： $O (n)$ 。最坏情况下，二叉树退化成一条链，递归需要 $O (n)$ 的栈空间。

方法二：自顶向下

Python 解法3C++ 解法3

python

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        ans = 0
        def dfs(node: Optional[TreeNode], depth: int) -> None:
            if node is None:
                return
            depth += 1
            nonlocal ans
            ans = max(ans, depth)
            dfs(node.left, depth)
            dfs(node.right, depth)
        dfs(root, 0)
        return ans

cpp

// C++ 版待补充

C++ 解法4

cpp

class Solution {
public:
    int maxDepth(TreeNode* root) {
        int ans = 0;
        auto dfs = [&](this auto&& dfs, TreeNode* node, int depth) -> void {
            if (node == nullptr) {
                return;
            }
            depth++;
            ans = max(ans, depth);
            dfs(node->left, depth);
            dfs(node->right, depth);
        };
        dfs(root, 0);
        return ans;
    }
};

复杂度分析

时间复杂度： $O (n)$ ，其中 $n$ 为二叉树的节点个数。
空间复杂度： $O (n)$ 。最坏情况下，二叉树退化成一条链，递归需要 $O (n)$ 的栈空间。

注

我在网上看到一种理解递归的说法：「在写递归函数时，可以假设递归返回的结果一定是正确的」。其实这种说法本质上就是数学归纳法。

更多相似题目，见题单链表、二叉树与一般树。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

视频讲解 ​

方法一：自底向上 ​

复杂度分析 ​

方法二：自顶向下 ​

复杂度分析 ​

注 ​

分类题单 ​

视频讲解

方法一：自底向上

复杂度分析

方法二：自顶向下

复杂度分析

注

分类题单