输入一棵二叉树的根节点,求该树的深度。从根节点到叶节点依次经过的节点(含根、叶节点)形成树的一条路径,最长路径的长度为树的深度。
例如:
给定二叉树 [3,9,20,null,null,15,7],3 / \ 9 20 / \ 15 7
返回它的最大深度 3 。
解题思路:
实际上是一个后序遍历,拿到左右子树中的较大深度,然后加1返回。
递归函数:
- 递归参数: 根节点 $root$。
- 终止条件: $root$ 为 $null$ 时,直接返回。
- 递推工作:
- 递归计算左子树的深度 $dl$ ;
- 递归计算右子树的深度 $dr$;
- 比较 $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)$。
评论区