给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
返回它的最大深度 3 。
递归
前序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
int max = 0;
public int maxDepth(TreeNode root) {
traversal(root,1);
return max;
}
public void traversal(TreeNode root, int d){
if(root == null) return;
max = Math.max(max, d);
traversal(root.left, d + 1);
traversal(root.right, d + 1);
}
}
|
后续遍历
1
2
3
4
5
6
7
8
9
| class Solution {
public int maxDepth(TreeNode root) {
if(root==null) return 0;
int left_depth = maxDepth(root.left);
int right_depth = maxDepth(root.right);
return 1 + Math.max(left_depth,right_depth);
}
}
|
迭代法（层次遍历）
同样适用于求n叉树的深度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class solution {
public int maxDepth(TreeNode root) {
if(root == null) {
return 0;
}
Deque<TreeNode> deque = new LinkedList<>();
deque.offer(root);
int depth = 0;
while (!deque.isEmpty()) {
int size = deque.size();
depth++;
for (int i = 0; i < size; i++) {
TreeNode node = deque.poll();
if (node.left != null) {
deque.offer(node.left);
}
if (node.right != null) {
deque.offer(node.right);
}
}
}
return depth;
}
}
|