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

return4.

思路分析：

这道题的思路应该是自下而上（post order traverse）来进行逐个subtree的判断。但是我在这道题上犯了一个严重的错误，那就是题目中说uni-value subtree上的所有节点的value都应该一样，而我在第一次实现的时候只是对比了root节点跟它的左右节点的value是不是一样，这样就很明显不对。下面就是我做的错误的实现方式，思路还是比较清晰的，就是考虑得不全面。

class Solution {
    public int countUnivalSubtrees(TreeNode root) {
        if(root == null) return 0;
        if(root.left == null && root.right == null) return 1;
        int left = countUnivalSubtrees(root.left);
        int right = countUnivalSubtrees(root.right);
        if(root.left == null) return right + (root.right.val == root.val ? 1 : 0);  <<< wrong comparison
        if(root.right == null) return left + (root.left.val == root.val ? 1 : 0);
        return right + left + (root.right.val == root.val && root.left.val == root.val ? 1 : 0);
    }
}

通过分析发现还是要通过post order traverse的方式，但是要借助一个辅助函数来判断当前节点为根节点的subtree是不是一个uni-value subtree，如果下面的subtree已经不是uni-value subtree了，那么上面的跟这个subtree相关联的subtree也就都不是uni-value subtree了。

class Solution {
    public int countUnivalSubtrees(TreeNode root) {
        if(root == null) return 0;
        int[] uniValueNum = new int[1];
        isUnivalSubtrees(root, uniValueNum);
        return uniValueNum[0];
    }
    public boolean isUnivalSubtrees(TreeNode root, int[] uniValueNum){
        if (root == null) return true;
        boolean left = isUnivalSubtrees(root.left, uniValueNum);
        boolean right = isUnivalSubtrees(root.right, uniValueNum);
        if(left && right){
            if(root.left!=null && root.left.val!=root.val) return false;
            if(root.right!=null && root.right.val!=root.val) return false;
            uniValueNum[0] ++;
            return true;
        }
        return false;
    }
}