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