⭐️ 题目日期：

百度 - 2024/8/13

🌳 题目描述：

给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

示例 1：

输入：root = [12, 5, 15, null, null, 13, 20]

输出：3

图解如下：

🕵🏽 面试评估：

这道题主要考察候选人能否使用深度优先搜索（DFS）或广度优先搜索（BFS）来遍历二叉树。

🧗难度系数：

⭐️ ⭐️

📝思路分析：

以案例所示的二叉树进行分析，

按照递归的方式，我们可以得到以下图解：

对于二叉树的最大深度问题，我们可以采用递归的方法来求解。

二叉树的最大深度定义为根节点到最远叶子节点的最长路径上的节点数。递归计算左子树和右子树的最大深度，然后取两者中的较大值，再加上 1（根节点这一层）就是整个二叉树的最大深度。

递归的基本情况是当节点为 null 时，此时深度为 0，表示已经到达叶子节点的下一层（空节点层）。

💻代码(Java、Python)：

Java

    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        return Math.max(leftDepth, rightDepth) + 1;
    }

Python

    def maxDepth(root):
        if root is None:
            return 0
    
        left_depth = maxDepth(root.left)
        right_depth = maxDepth(root.right)
        return max(left_depth, right_depth) + 1

🚵🏻复杂度分析：

时间复杂度：O(n)，n 为节点个数

空间复杂度：O(h)，h 为树的深度。对于完全二叉树，树的高度为 logn, 所以空间复杂度为 O(log ⁡n)；最坏情况下，每个节点都只有一个子节点，树的高度为节点的个数，空间复杂度为 O(n)

🔬在线评测(Online Judge):

题目链接