-
Notifications
You must be signed in to change notification settings - Fork 0
/
MinimumDepthOfBinaryTree.java
98 lines (82 loc) · 2.7 KB
/
MinimumDepthOfBinaryTree.java
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
package algorithm.topics.binarytree;
import algorithm.leetcode.domain.TreeNode;
import java.util.LinkedList;
import java.util.Queue;
/**
* 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.
* <p>
* Reference: <a href="https://leetcode.cn/problems/minimum-depth-of-binary-tree/">Minimum Depth of Binary Tree</a>
* Difficulty: Easy
*
* @author hufeng
* @version MinimumDepthOfBinaryTree.java, v 0.1 21/11/2017 12:25 AM Exp $
*/
public class MinimumDepthOfBinaryTree {
static int minDepth = Integer.MAX_VALUE;
public static int minDepth(TreeNode root) {
if (root == null)
return 0;
postOrderTraverse(root, 1, (root.left == null && root.right == null));
return minDepth;
}
private static void postOrderTraverse(TreeNode node, int depth, boolean isLeaf) {
if (node == null) {
return;
}
if (isLeaf) {
minDepth = Math.min(minDepth, depth);
}
postOrderTraverse(node.left, depth + 1, (node.left != null && node.left.left == null && node.left.right == null));
postOrderTraverse(node.right, depth + 1, (node.right != null && node.right.left == null && node.right.right == null));
}
// Good solution
/**
* 深度优先搜索 DSF
*
* @param root
* @return
*/
public static int minDepthMethod2(TreeNode root) {
if (root == null) return 0;
int left = minDepthMethod2(root.left);
int right = minDepthMethod2(root.right);
return (left == 0 || right == 0) ? left + right + 1 : Math.min(left, right) + 1;
}
class QueueNode {
TreeNode node;
int depth;
public QueueNode(TreeNode node, int depth) {
this.node = node;
this.depth = depth;
}
}
/**
* 广度优先搜索 BSF
*
* @param root
* @return
*/
public int minDepth3(TreeNode root) {
if (root == null) {
return 0;
}
Queue<QueueNode> queue = new LinkedList<QueueNode>();
queue.offer(new QueueNode(root, 1));
while (!queue.isEmpty()) {
QueueNode nodeDepth = queue.poll();
TreeNode node = nodeDepth.node;
int depth = nodeDepth.depth;
if (node.left == null && node.right == null) {
return depth;
}
if (node.left != null) {
queue.offer(new QueueNode(node.left, depth + 1));
}
if (node.right != null) {
queue.offer(new QueueNode(node.right, depth + 1));
}
}
return 0;
}
}