侧边栏壁纸
博主头像
Lin2J博主等级

升级了服务器,访问应该会更加流畅🇨🇳

  • 累计撰写 94 篇文章
  • 累计创建 39 个标签
  • 累计收到 4 条评论

目 录CONTENT

文章目录

55-Ⅰ二叉树的深度

Lin2J
2021-07-21 / 0 评论 / 0 点赞 / 153 阅读 / 804 字 / 正在检测是否收录...

剑指 Offer 55 - I. 二叉树的深度

输入一棵二叉树的根节点,求该树的深度。从根节点到叶节点依次经过的节点(含根、叶节点)形成树的一条路径,最长路径的长度为树的深度。
例如:
给定二叉树 [3,9,20,null,null,15,7],

   3
  / \
 9  20
   /  \
  15   7

返回它的最大深度 3 。

解题思路:

实际上是一个后序遍历,拿到左右子树中的较大深度,然后加1返回。

递归函数:

  • 递归参数: 根节点 $root$。
  • 终止条件: $root$ 为 $null$ 时,直接返回。
  • 递推工作:
    1. 递归计算左子树的深度 $dl$ ;
    2. 递归计算右子树的深度 $dr$;
    3. 比较 $dl$ 和 $dr$ ,选择较大者然后加一返回。

代码:

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

复杂度分析:

  • 时间复杂度$O(N)$:$N$ 为树节点的个数,计算深度需要遍历所有的节点。
  • 空间复杂度$O(N)$:最长情况下,需要进行 $N$ 次递归,需要栈空间为 $O(N)$。
0

评论区