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

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

  • 最终答案不会超过 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

上一篇:LintCode领扣 题解丨字节跳动高频题:最长上升子序列


下一篇:LintCode 题解丨阿里巴巴面试题:第k大元素