/*
Solution1:
key to solve: DFS, recursion
1.Classic DFS recursion
*/
public int minDepthDFS(TreeNode root) {
//base case
if (root == null) return 0;
//recursion
int left = minDepthDFS(root.left);
int right = minDepthDFS(root.right);
if (left == 0) return left+1;
if (right == 0) return right+1;
return Math.min(left, right) + 1;
}
/*
Solution2: BFS ArrayList
Key to solve: BFS, ArrayList similar with Maximum Depth
1. the initial depth value start from 1;
2. Go through Tree by level => BFS
*/
private int minDepthBFS(TreeNode root){
if(root==null) return 0;
List<TreeNode> treeList=new ArrayList<TreeNode>();
//start from 1
int depth=1;
treeList.add(root);
while(!treeList.isEmpty()){
List<TreeNode> cur=new ArrayList<TreeNode>();
for(TreeNode t:treeList) {
if (t.left == null && t.right == null) return depth;
if (t.left != null) cur.add(t.left);
if (t.right != null) cur.add(t.right);
}
//clone the current level to TreeList
treeList=new ArrayList<TreeNode>(cur);
depth++;
}
return depth;
}