2015年10月3日星期六

Leetcode 104 Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Solution 1: recursive DFS
 public class Solution {  
   public int maxDepth(TreeNode root) {  
     int[] res=new int[1];  
     dfs(root,0,res);  
     return res[0];  
   }  
   private void dfs(TreeNode x, int d, int[] res) {  
     if (x==null) return;  
     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, use 2 queue to count the depth.
 public class Solution {  
   public int maxDepth(TreeNode root) {  
     Queue<TreeNode> q1=new LinkedList<>();  
     Queue<TreeNode> q2=new LinkedList<>();  
     if (root==null) return 0;  
     int d=0;  
     q1.offer(root);  
     while (!q1.isEmpty()) {  
       while (!q1.isEmpty()) {  
         TreeNode x=q1.poll();  
         if (x.left!=null) q2.offer(x.left);  
         if (x.right!=null) q2.offer(x.right);  
       }  
       Queue<TreeNode> temp=q1;  
       q1=q2;  
       q2=temp;  
       d++;  
     }  
     return d;  
   }  
 }  

没有评论:

发表评论