104. 二叉树的最大深度
给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
示例 1：
输入： root = [3,9,20,null,null,15,7]
输出： 3
示例 2：
输入： root = [1,null,2]
输出： 2
提示：
- 树中节点的数量在 [ 0 , 1 0 4 ] [0, 10^4] [0,104] 区间内。
- − 100 ≤ N o d e . v a l ≤ 100 -100 \leq Node.val \leq 100 −100≤Node.val≤100
解法一(BFS+队列)
思路分析：
- 使用层序遍历对二叉树进行遍历，在遍历二叉树的过程中，记录遍历的层数
实现代码如下：
class Solution {
public int maxDepth(TreeNode root) {
int ans = 0;
if (root == null)
return ans; // 边界条件
Queue<TreeNode> queue = new ArrayDeque<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
++ ans; // 记录层数
for (int i = 0; i < size; ++ i) {
TreeNode node = queue.poll();
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
}
return ans;
}
}
提交结果如下：
解答成功:
执行耗时:1 ms,击败了22.08% 的Java用户
内存消耗:41.6 MB,击败了8.86% 的Java用户
复杂度分析：
-
时间复杂度： O ( n ) O(n) O(n)
-
空间复杂度： O ( n ) O(n) O(n)
解法二(前序求深度+递归)
思路分析：
-
根据dfs递归遍历二叉树，并在遍历的过程标记某二叉树的节点所在层数
-
即递归参数主要有两个，一个是二叉树结点，另一个是该节点所在层数
-
递归边界条件，即为结点为空时，不再往下遍历
-
递归过程，即比较该层是否为最大深度即可
实现代码如下：
class Solution {
int ans = 0;
public int maxDepth(TreeNode root) {
getMaxDepth(root, 1);
return ans;
}
private void getMaxDepth(TreeNode node, int depth) {
if (node == null)
return ;
ans = Math.max(ans, depth);
getMaxDepth(node.left, depth+1);
getMaxDepth(node.right, depth+1);
}
}
提交结果如下：
解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:41.3 MB,击败了16.72% 的Java用户
复杂度分析：
-
时间复杂度： O ( n ) O(n) O(n)
-
空间复杂度： O ( n ) O(n) O(n)，考虑递归对栈的消耗
解法三(后序求高度+递归)
思路分析：
-
对于该题，首先注意一个细节，对于该题求根节点的高度即等同于求根节点的最大深度
-
所以，可以使用 后序遍历求二叉树的最大高度，即根节点的高度来得到二叉树的最大深度。
-
然后思考递归的参数和返回值；对于该题递归的参数只有二叉树的节点，返回值即为该节点的高度
-
然后思考递归的边界条件；即当该节点为
null时，此时节点高度为0，返回即可 -
对于递归的过程，则先求左右孩子节点的高度，然后得出最大值，再加一，则得出该节点的高度，返回即可。
实现代码如下：
class Solution {
public int maxDepth(TreeNode root) {
return getHeight(root);
}
// 后序遍历求二叉树某节点的高度
private int getHeight(TreeNode node) {
if (node == null)
return 0; // 为空时 节点高度为0
// 左
int leftHeight = getHeight(node.left);
// 右
int rightHeight = getHeight(node.right);
// 中
int height = Math.max(leftHeight, rightHeight) + 1;
return height; // 返回该节点高度
}
}
提交结果如下：
解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:41.3 MB,击败了18.91% 的Java用户
复杂度分析：
-
时间复杂度： O ( n ) O(n) O(n)
-
空间复杂度： O ( n ) O(n) O(n)，考虑递归的空间消耗