# 250     Count Univalue Subtrees

## 250. [Count Univalue Subtrees](https://leetcode.com/problems/count-univalue-subtrees/description/)

## 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
```

return`4`.

## 2. Implementation

**(1) DFS + post order traversal**

```java
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)