长大后想做什么?做回小孩!

0%

LeetCode——二叉树的最大深度

NO.104 二叉树的最大深度 简单

GxdqsO.png

思路一:深搜 最直接的想法深搜。

1
2
3
4
5
6
7
8
9
10
11
12
13
public int maxDepth(TreeNode root) {
return dfs(root);
}

private int dfs(TreeNode root) {
if (root == null) return 0;
int max1 = 0, max2 = 0;
//求左子树最深,右子树最深
max1 += dfs(root.left);
max2 += dfs(root.right);
//左右子树最深的加上根的一层深度
return Math.max(max1, max2) + 1;
}

时间复杂度:O(n) 像是前序遍历。

思路二:广搜 广搜也是可以的,层序遍历,每遍历一层深度+1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int maxDepth(TreeNode root) {
int depth = 0;
if (root == null) return depth;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
//层序遍历
while (!queue.isEmpty()) {
depth++;
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode poll = queue.poll();
if (poll.left != null) queue.add(poll.left);
if (poll.right != null) queue.add(poll.right);
}
}
return depth;
}

时间复杂度:O(n) 层序遍历。


本人菜鸟,有错误请告知,感激不尽!

更多题解和源码:github