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:

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */public class Solution {    public class UniValueCount {        int value;        boolean isUniValue;        int count;        public UniValueCount(int v, boolean is, int num){            value = v;            isUniValue = is;            count = num;        }    }    public int countUnivalSubtrees(TreeNode root) {        UniValueCount res = countUnivalRecur(root);        return res.count;    }        public UniValueCount countUnivalRecur(TreeNode cur){        if (cur==null){            return new UniValueCount(0,false,0);        }        if (cur.left==null && cur.right==null){            return new UniValueCount(cur.val,true,1);        }                UniValueCount res = new UniValueCount(0,true,0);        if (cur.left!=null){            UniValueCount leftRes = countUnivalRecur(cur.left);            res.isUniValue = res.isUniValue && (leftRes.isUniValue && cur.val==leftRes.value);            res.count += leftRes.count;        }        if (cur.right!=null){            UniValueCount rightRes = countUnivalRecur(cur.right);            res.isUniValue = res.isUniValue && (rightRes.isUniValue && cur.val==rightRes.value);            res.count += rightRes.count;        }        if (res.isUniValue){            res.count++;            res.value = cur.val;        }        return res;    }}