# 250. Count Univalue Subtrees

### Leetcode

<https://leetcode.com/problems/count-univalue-subtrees/>

### 題目

Given the `root` of a binary tree, return the number of **uni-value** subtrees.

A **uni-value subtree** means all nodes of the subtree have the same value.

&#x20;

**Example 1:**

![](https://assets.leetcode.com/uploads/2020/08/21/unival_e1.jpg)

```
Input: root = [5,1,5,5,5,null,5]
Output: 4
```

**Example 2:**

```
Input: root = []
Output: 0
```

**Example 3:**

```
Input: root = [5,5,5,5,5,null,5]
Output: 6
```

what is univalue ?

If the node meets one of the following criteria:

1. The node has no children (base case)
2. All of the node's children are univalue subtrees, and the node and its children all have the same value

### 解答 <a href="#ti-jie" id="ti-jie"></a>

* **方法一**

```
var countUnivalSubtrees = function(root) {
    let count = 0;
    
    const helper = (node) => {
        if (!node) return [true];
        
        const val = node.val;
        
        if (!node.left && !node.right) {
            count++;
            return [true, val]
        }
        
        // node.left 是 null 的話，預設帶 leftValue 等於本身的 val
        const [isLeftUnival, leftValue = val] = helper(node.left);
        const [isRightUnival, rightValue = val] = helper(node.right);
        const isValueSame = val === leftValue && val === rightValue;
        const isUniVal = isLeftUnival && isRightUnival && isValueSame;
        if (isUniVal) count++;
        
        return [isUniVal, val]
    }
    
    helper(root);
    return count;
};
```

Runtime: 117 ms, faster than 20.31% of JavaScript online submissions for Count Univalue Subtrees.

Memory Usage: 45.3 MB, less than 7.08% of JavaScript online submissions for Count Univalue Subtrees.

* **方法二**

```
var countUnivalSubtrees = function(root) {
    let count = 0;
    
    const isUnival = (node, parentVal) => {
        if (!node) return true;
        
        const nodeVal = node.val;
        const conditions = [isUnival(node.left, nodeVal), isUnival(node.right, nodeVal)];
        // 使用 every 確保左右的節點都跑完 isUnival function
        if (!conditions.every(condition => condition)) {
           return false; 
        }
        
        // 左右節點都是 isUnival 的話就可以 count+1 了
        count++;
        return nodeVal === parentVal;
    }
    
    // 初始值帶入超過上限 1000 的 parentVal
    isUnival(root, 1001);
    return count;
};
```

Runtime: 72 ms, faster than 90.15% of JavaScript online submissions for Count Univalue Subtrees.

Memory Usage: 44.9 MB, less than 24.00% of JavaScript online submissions for Count Univalue Subtrees.
