大厂面试真题详解：二叉树的最大深度

给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的距离。

• 最终答案不会超过 5000

在线评测地址：领扣题库官网

样例 1:

输入: tree = {}
输出: 0       

样例解释: 空树的深度是0。
样例 2:

输入: tree = {1,2,3,#,#,4,5}
输出: 3

样例解释: 树表示如下，深度是3
1
/
2 3

/ \                

4 5
它将被序列化为{1,2,3,#,#,4,5}

解题思路

• 思路

  • 这道题用DFS（深度优先搜索）来解答。我们知道，每个节点的深度与它左右子树的深度有关，且等于其左右子树最大深度值加上 1。

• 递归设计

  • 递归条件（recursive case）: 对于当前节点root，我们求出左右子树的深度的最大值，再加1表示当前节点的深度，返回该数值，即为以root为根节点的树的最大深度。
  • 终止条件（base case）：当前节点为空时，认为树深为0。

复杂度分析

• 时间复杂度：O(n)，其中 n是节点的数量。我们每个节点只访问一次，因此时间复杂度为 O(n)。

• 空间复杂度：考虑到递归使用调用栈（call stack）的情况。

  • 最坏情况：树完全不平衡。例如每个节点都只有左节点，此时将递归n 次，需要保持调用栈的存储为O(n)
  • 最好情况：树完全平衡。即树的高度为 log(n)，此时空间复杂度为 O(log(n))

代码

public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: An integer
     */
    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;
    }
}

更多题解参考：九章官网solution