250. Count Univalue Subtrees.md

Solution1

class Solution {
    public int countUnivalSubtrees(TreeNode root) {
        int[] cnt = {0};
        checkUni(root, cnt);
        return cnt[0];
    }
    private boolean checkUni(TreeNode root, int[] cnt) {
        if (root == null) {
            return true;
        }
        boolean left = checkUni(root.left, cnt);
        boolean right = checkUni(root.right, cnt);
        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;
            }
            cnt[0]++;
            return true;
        }
        return false;
    }
}

note

• time O(n) space O(n)
• The idea is to apply post order traversal thinking. While at each node, we update the result counter, we also check if the left and right subtree return true(which means left and right subtree have univalue respectively). So what do we return in the current stack? We are going to check if the current node is univalue with its left and right subtrees and return true if they are, or false if they are not. So basically, the two recursive calls help us traverse to leaves and them bottom up.