Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
| public class MinimumDepthOfBinaryTree {
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
return helper(root, 1);
}
private int helper(TreeNode node, int length) {
if (node == null) {
return length - 1;
}
if (node.left == null && node.right == null) {
return length;
} else {
int l = Integer.MAX_VALUE;
int r = Integer.MAX_VALUE;
if (node.left != null) {
l = helper(node.left, length + 1);
}
if (node.right != null) {
r = helper(node.right, length + 1);
}
return Math.min(l, r);
}
}
public int minDepthSolution2(TreeNode root) {
if(root == null) {
return 0;
}
int nextLevelCount = 1;
int counter = 0;
int depth = 1;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()) {
TreeNode node = queue.poll();
nextLevelCount--;
if(node.left == null && node.right == null) {
return depth;
}
if(node.left != null) {
queue.add(node.left);
counter++;
}
if(node.right != null) {
queue.add(node.right);
counter++;
}
if(nextLevelCount == 0) {
nextLevelCount = counter;
counter = 0;
depth++;
}
}
return 0;
}
}
|