LeetCode 250: Count Univalue Subtrees | CrazyEgg

LeetCode: Count Univalue Subtrees | CrazyEgg
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.

Best -
http://www.cnblogs.com/yrbbest/p/5011791.html
int count = 0;

    
    public int countUnivalSubtrees(TreeNode root) {
        if (root == null) return 0;
        isUnival(root);
        return count;
    }
    
    private boolean isUnival(TreeNode root) {
        if (root == null) return true;
        if (isUnival(root.left) & isUnival(root.right)) {
            if (root.left != null && root.left.val != root.val) return false;
            if (root.right != null && root.right.val != root.val) return false;
            count++;
            return true;
        }
        return false;
    }

http://happycoding2010.blogspot.com/2015/11/leetcode-250-count-univalue-subtrees.html
https://discuss.leetcode.com/topic/20721/my-concise-java-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;  
   }  

http://likemyblogger.blogspot.com/2015/08/leetcode-250-count-univalue-subtrees.html

    int countUnivalSubtrees(TreeNode* root) {

        int cnt = 0;

        helper(root, cnt);

        return cnt;

    }

    bool helper(TreeNode* root, int &cnt){

        if(!root) return true;

        bool left = helper(root->left, cnt);

        bool right = helper(root->right, cnt);

        if(!left || !right) return false;

        if(root->left && root->left->val!=root->val) return false;

        if(root->right && root->right->val!=root->val) return false;

        cnt++;

        return true;

    }

    public int countUnivalSubtrees(TreeNode root) {
        if (root == null) {
            return 0;
        }

        if (root.left == null && root.right == null) {
            return 1;
        }

        int[] result = new int[]{0};
        helper(root, result);
        return result[0];
    }

    private boolean helper(TreeNode root, int[] result) {

        if (root.right == null && root.left == null) {
            result[0]++;
            return true;
        } else if (root.right != null && root.left == null) { 

            //don't check precondition before recursive-the base condition check does it.
            if (helper(root.right, result) && root.val == root.right.val) {
                result[0]++;
                return true;
            } else {
                return false;
            }
        } else if (root.right == null) {
            if (helper(root.left, result) && root.val == root.left.val) {
                result[0]++;
                return true;
            } else {
                return false;
            }
        } else {
            boolean l = helper(root.right, result);
            boolean r = helper(root.left, result);
            if (l && r && root.val == root.left.val && root.val == root.right.val) {
                result[0]++;
                return true;
            } else {
                return false;
            }
        }

    }

http://ying.ninja/?p=886

public int countUnivalSubtrees(TreeNode root) {

    int[] count = new int[1];

    isUnivalSubtrees(root, count);

    return count[0];

}

public boolean isUnivalSubtrees(TreeNode root, int[] count) {

    if (root == null) {

        return false; // return true - make code cleaner

    }

    boolean left = isUnivalSubtrees(root.left, count);

    boolean right = isUnivalSubtrees(root.right, count);

    if (!left && !right) {

        if (root.left == null && root.right == null) {

            count[0]++;

            return true;

        }

    } else if (left && right) {

        if (root.left.val == root.val && root.right.val == root.val) {

            count[0]++;

            return true;

        }

    } else if (left && !right) {

        if (root.right == null && root.left.val == root.val) {

            count[0]++;

            return true;

        }

    } else if (!left && right) {

        if (root.left == null && root.right.val == root.val) {

            count[0]++;

            return true;

        }

    }

    return false;

}

https://github.com/algorhythms/LeetCode/blob/master/250%20Count%20Univalue%20Subtrees.py
http://buttercola.blogspot.com/2015/09/leetcode-count-univalue-subtrees.html

X. Not efficient
https://discuss.leetcode.com/topic/55470/is-there-a-dp-solution-for-this-problem

    int ret = 0;
    public int countUnivalSubtrees(TreeNode root) {
        helper(root);
        return ret;
    }
    private void helper(TreeNode root){
        if(root==null) return;
        if(isUni(root)) ret++;
        helper(root.left);
        helper(root.right);
    }
    private boolean isUni(TreeNode root){
        if(root==null || (root.left==null && root.right==null)) return true;
        if(root.left!=null && root.val!=root.left.val) return false;
        if(root.right!=null && root.val!=root.right.val) return false;
        return (isUni(root.left) && isUni(root.right));
    }

Read full article from LeetCode: Count Univalue Subtrees | CrazyEgg