# 250. (Locked)Count Univalue Subtrees

Difficulty: Medium

Frequency: N/A

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

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int countUnivalSubtrees(TreeNode* root) {
int cnt = 0;
countSubtree(root, cnt);
return cnt;
}
bool countSubtree(TreeNode* node, int& cnt) {
if (!node) return false;
if (!node->left && !node->right) {
cnt++;
return true;
}
bool left = countSubtree(node->left, cnt);
bool right = countSubtree(node->right, cnt);
if (left && right && (!node->left || node->left->val == node->val) && (!node->right || node->right->val == node->val)) {
cnt++;
return true;
}
return false;
}
}
```

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn: