The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
NOTE : The path has to end on a leaf node.
Example :
1
/
2
min depth = 2.
Method 1:
Level order traversal/BFS
Solution:
Time: O(n) Space: O(n)
/** * Definition for binary tree * class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { * val = x; * left=null; * right=null; * } * } */ public class Solution { public int minDepth(TreeNode A) { Deque<TreeNode> queue = new ArrayDeque<>(); int min = 0; TreeNode curr = A; queue.add(curr); while (!queue.isEmpty()) { min ++; int size = queue.size(); for (int i = 0; i < size; i ++) { TreeNode node = queue.poll(); if (node.left == null && node.right == null) { return min; } if (node.left != null) { queue.add(node.left); } if (node.right != null) { queue.add(node.right); } } } return min; } }
Method 2:
DFS
Solution:
Time: O(n) Space: O(1)
/** * Definition for binary tree * class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { * val = x; * left=null; * right=null; * } * } */ public class Solution { public int minDepth(TreeNode A) { if (A == null) { return 0; } if (A.left == null && A.right == null) { return 1; } if (A.left == null) { return minDepth(A.right) + 1; } if (A.right == null) { return minDepth(A.left) + 1; } int left = minDepth(A.left); int right = minDepth(A.right); return Math.min(left, right) + 1; } }