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.
Solution 1: recursive DFS
public class Solution {
public int minDepth(TreeNode root) {
int[] res=new int[1];
if (root==null) return 0;
res[0]=Integer.MAX_VALUE;
dfs(root,0,res);
return res[0];
}
private void dfs(TreeNode x, int d, int[] res) {
if (x==null) return;
if (x.left==null && x.right==null) {
if (d+1<res[0]) res[0]=d+1;
}
dfs(x.left,d+1,res);
dfs(x.right,d+1,res);
}
}
Solution 2: iterative BFS
public class Solution {
public int minDepth(TreeNode root) {
Queue<TreeNode> q1=new LinkedList<>();
Queue<TreeNode> q2=new LinkedList<>();
if (root==null) return 0;
int d=0, res=Integer.MAX_VALUE;
q1.offer(root);
while (!q1.isEmpty()) {
while (!q1.isEmpty()) {
TreeNode x=q1.poll();
if (x.left==null && x.right==null) {
if (d+1<res) res=d+1;
}
if (x.left!=null) q2.offer(x.left);
if (x.right!=null) q2.offer(x.right);
}
d++;
Queue<TreeNode> temp=q1;
q1=q2;
q2=temp;
}
return res;
}
}
没有评论:
发表评论