LeetCode 250: Count Univalue Subtrees

Explanation:

To solve this problem, we can perform a bottom-up approach using recursion. We will traverse the tree in a post-order manner and check if each subtree is a univalue subtree. A subtree is considered a univalue subtree if all nodes in the subtree have the same value.

1. We define a recursive function countUnivalSubtrees that returns a boolean indicating if the subtree rooted at the current node is a univalue subtree, along with the count of univalue subtrees found in the subtree.
2. We recursively call the function on the left and right children of the current node.
3. If both the left and right subtrees are univalue subtrees and the current node's value is equal to its children's values (if present), then we increment the count and return true.
4. Otherwise, we return false.

Time Complexity: O(N) - where N is the number of nodes in the tree Space Complexity: O(H) - where H is the height of the tree

class Solution {
    int count = 0;
    
    public int countUnivalSubtrees(TreeNode root) {
        isUnivalSubtree(root);
        return count;
    }
    
    private boolean isUnivalSubtree(TreeNode node) {
        if (node == null) {
            return true;
        }
        
        boolean left = isUnivalSubtree(node.left);
        boolean right = isUnivalSubtree(node.right);
        
        if ((node.left == null || node.left.val == node.val) && 
            (node.right == null || node.right.val == node.val) &&
            left && right) {
            count++;
            return true;
        }
        
        return false;
    }
}