Skip to content

Commit 3257c2b

Browse files
Steve SunSteve Sun
authored andcommitted
minimum depth of binary tree
1 parent cdb4bb8 commit 3257c2b

File tree

2 files changed

+51
-0
lines changed

2 files changed

+51
-0
lines changed
Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
package easy;
2+
3+
import java.util.LinkedList;
4+
import java.util.Queue;
5+
6+
import classes.TreeNode;
7+
8+
public class MinimumDepthofBinaryTree {
9+
/**We can solve this problem using both BFS and DFS:
10+
* DFS is to visit every single root to leaf path and return the shortest one.
11+
* BFS is to visit every level and return whenever we find the first leaf node.*/
12+
public int minDepth(TreeNode root) {
13+
if(root == null) return 0;
14+
int left = minDepth(root.left);
15+
int right = minDepth(root.right);
16+
if(left == 0) return right+1;
17+
if(right == 0) return left+1;
18+
return Math.min(left, right)+1;
19+
}
20+
21+
public static void main(String[] args){
22+
MinimumDepthofBinaryTree test = new MinimumDepthofBinaryTree();
23+
TreeNode root = new TreeNode(1);
24+
root.left = new TreeNode(2);
25+
root.right = new TreeNode(3);
26+
System.out.println(test.minDepth(root));
27+
}
28+
29+
30+
public int minDepth_BFS(TreeNode root) {
31+
if(root == null) return 0;
32+
Queue<TreeNode> q = new LinkedList();
33+
q.offer(root);
34+
int level = 0;
35+
while(!q.isEmpty()){
36+
level++;
37+
int size = q.size();
38+
for(int i = 0; i < size; i++){
39+
TreeNode curr = q.poll();
40+
if(curr.left != null) q.offer(curr.left);
41+
if(curr.right != null) q.offer(curr.right);
42+
if(curr.left == null && curr.right == null) return level;
43+
}
44+
}
45+
return level;
46+
}
47+
48+
49+
50+
}

README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -31,6 +31,7 @@
3131
|121|[Best Time to Buy and Sell Stock](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/)|[Solution](../../blob/master/EASY/src/easy/BestTimeToBuyAndSellStock.java)| O(n)|O(1) | Easy| DP
3232
|117|[Populating Next Right Pointers in Each Node II](https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/)|[Solution](../../blob/master/HARD/src/hard/PopulatingNextRightPointersinEachNodeII.java)| O(n)|O(1) | Hard| BFS
3333
|116|[Populating Next Right Pointers in Each Node](https://leetcode.com/problems/populating-next-right-pointers-in-each-node/)|[Solution](../../blob/master/MEDIUM/src/medium/PopulatingNextRightPointersinEachNode.java)| O(n)|O(1) | Medium| BFS
34+
|111|[Minimum Depth of Binary Tree](https://leetcode.com/problems/minimum-depth-of-binary-tree/)|[Solution](../../blob/master/EASY/src/easy/MinimumDepthofBinaryTree.java)| O(n)|O(1)~O(h) | Easy| BFS, DFS
3435
|91|[Decode Ways](https://leetcode.com/problems/decode-ways/)|[Solution](../../blob/master/MEDIUM/src/medium/DecodeWays.java)| O(n)|O(n) | Medium| DP
3536
|98|[Validate Binary Search Tree](https://leetcode.com/problems/validate-binary-search-tree/)|[Solution] | O(n) | O(1) | Medium | DFS/Recursion
3637
|79|[Word Search](https://leetcode.com/problems/word-search/)|[Solution](../../blob/master/MEDIUM/src/medium/WordSearch.java)|O(m*n*l) ? |O(m*n)|Medium|Backtracking/DFS

0 commit comments

Comments
 (0)