2015年10月4日星期日

Leetcode 111 Minimum Depth of Binary Tree

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;  
   }  
 }  

没有评论:

发表评论