250 Count Univalue Subtrees

250. Count Univalue Subtrees

1. Question

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.

2. Implementation

(1) DFS + post order traversal

class Solution {
    public int countUnivalSubtrees(TreeNode root) {
        int[] res = new int[1];
        postOrderTraverse(root, res);
        return res[0];
    }

    public boolean postOrderTraverse(TreeNode node, int[] res) {
        if (node == null) {
            return true;
        }

        boolean left = postOrderTraverse(node.left, res);
        boolean right = postOrderTraverse(node.right, res);

        if (left && right) {
            if (node.left != null && node.left.val != node.val || 
                node.right != null && node.right.val != node.val) {
                return false;
            }
            ++res[0];
            return true;
        }
        return false;
    }
}

3. Time & Space Complexity

DFS: 时间复杂度是O(n), 空间复杂度是O(h)