2015年11月4日星期三

Leetcode 250 Count Univalue Subtrees

Given a binary tree, count the number of uni-value subtrees.
A Uni-value subtree means all nodes of the subtree have the same value.
For example:
Given binary tree,
              5
             / \
            1   5
           / \   \
          5   5   5
return 4.
Solution 1: recursive DFS
 public class Solution {  
   public int countUnivalSubtrees(TreeNode root) {  
     int[] count=new int[1];  
     dfs(root,count);  
     return count[0];  
   }  
   private boolean dfs(TreeNode x, int[] count) {  
     if (x==null) return true;  
     boolean left=dfs(x.left, count);  
     boolean right=dfs(x.right, count);  
     if (!left || !right) return false;  
     if (x.left!=null && x.val!=x.left.val) return false;  
     if (x.right!=null && x.val!=x.right.val) return false;  
     count[0]++;  
     return true;  
   }  
 }  

没有评论:

发表评论