来自Leetcode第104题二叉树的深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
递归I
如果根结点不为空，递归遍历左右子树，并且深度+1，最后返回最大值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| int max = 0;
int depth = 0;
public int maxDepth(TreeNode root) {
backOrder(root);
return max;
}
private void backOrder(TreeNode root) {
if (root != null) {
depth++;
max = Math.max(max, depth);
backOrder(root.left);
backOrder(root.right);
depth--;
}
}
|
递归II
1
2
3
4
5
6
7
8
| public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
} else {
int left_height = maxDepth(root.left);
int right_height = maxDepth(root.right);
return java.lang.Math.max(left_height, right_height) + 1;
}
|
迭代
来自题解的评论区
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
| public static class Pair{
TreeNode node;
int height;
public Pair(TreeNode node,int height){
this.node = node;
this.height = height;
}
}
public int maxDepth(TreeNode root){
if(root == null) return 0;
int depth = 1;
Stack<Pair> stack = new Stack<>();
stack.add(new Pair(root,1));
while (!stack.isEmpty()){
Pair pair = stack.pop();
TreeNode pop = pair.node;
depth = depth>pair.height?depth:pair.height;
if(pop.right!=null){
stack.add(new Pair(pop.right,pair.height+1));
}
if(pop.left!=null){
stack.add(new Pair(pop.left,pair.height+1));
}
}
return depth;
}
|