250. Count Univalue Subtrees

Problem:

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.

Analysis:
6/8/2018 
Helper returns whether the root is uni-value subtree and root's val equals to its parent's value. If both left and right return true, we know that left and right are uni-value subtree and their values equal to root.val. So there will be one more univalue subtree, the root plus its children.
--------------------------------------------------------------------------------------------------------------------------------------------

Think about what exactly makes a uni-value subtree.

1. left subtree is uni-value subtree

2. right subtree is uni-value subtree

3. left != null && right != null && left.val == right.val == root.val

Solution:

class Solution {
    int res = 0;
    public int countUnivalSubtrees(TreeNode root) {
        if (root == null) return res;
        helper(root, root.val);
        return res;
    }
    
    private boolean helper(TreeNode root, int val) {
        if (root == null)
            return true;
        boolean left = helper(root.left, root.val);
        boolean right = helper(root.right, root.val);
        if (left && right) 
            res++;
        return left && right && root.val == val;
    }
}