给定一个二叉树,找出其最大深度。
二叉树的深度为根节点到最远叶子节点的距离。
- 最终答案不会超过 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