# LeetCode – Count Univalue Subtrees

### 题目：

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.

Example :

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

5
/ \
1   5
/ \   \
5   5   5

Output: 4```

### 实现：

• 创建判断相同值子树方法isUnivalSubtrees， 判断其左、右节点与父节点是否相同，判定为Uni-value subtree（比较子节点与父节点val值时要先判断下对应left， right是否为空）， 分别判断左子树和右子树的是否为Uni-value subtree， 如果是计数器累加。
• isUnivalSubtrees 时间 复杂度O(n) 嵌入 countUnivalSubtrees后 O(n^2)
``````
/**
* Definition of TreeNode:
* class TreeNode {
* public:
*     int val;
*     TreeNode *left, *right;
*     TreeNode(int val) {
*         this->val = val;
*         this->left = this->right = NULL;
*     }
* }
*/

class Solution {
public:
/**
* @param root: the given tree
* @return: the number of uni-value subtrees.
*/
int countUnivalSubtrees(TreeNode * root) {
int total = 0;
if (root == nullptr){
return 0;
}
total = countUnivalSubtrees(root->left) + countUnivalSubtrees(root->right);
if (isUnivalSubtrees(root)){
total +=1;
}

}
private:
bool isUnivalSubtrees(TreeNode * root){
if (root == nullptr) {
return true;
}
if (root->left!=nullptr && root->left->val != root->val) {
return false;
}
if (root->right!=nullptr && root->right->val != root->val){
return false;
}
if (isUnivalSubtrees(root->left) && isUnivalSubtrees(root->right)){
return true;
}
return false;
}
};

``````

### 实现：

•  判断是否为Uni-value subtree的同时累计符合条件的子树数量，一起返回。
•  O(N)
``````/**
* Definition of TreeNode:
* class TreeNode {
* public:
*     int val;
*     TreeNode *left, *right;
*     TreeNode(int val) {
*         this->val = val;
*         this->left = this->right = NULL;
*     }
* }
*/

class Solution {
public:
/**
* @param root: the given tree
* @return: the number of uni-value subtrees.
*/
int countUnivalSubtrees(TreeNode * root) {
bool isUnival = true;
return helperCount(root, isUnival);

}
int helperCount(TreeNode *root, bool& isUnival) {
if (root == nullptr) {
isUnival = true;
return 0;
}
bool isLeftunival = true;
bool isRightunival = true;
int leftCount = 0;
int rightCount = 0;
leftCount = helperCount(root->left, isLeftunival);
rightCount = helperCount(root->right, isRightunival);
if (!isLeftunival || !isRightunival){
isUnival = false;
}
if (root->left !=nullptr && root->left->val != root->val ){
isUnival = false;
}
if (root->right !=nullptr && root->right->val != root->val ){
isUnival = false;
}
if (isUnival){
return leftCount+rightCount+1;
}
else {
return leftCount+rightCount;
}

}
};``````

### 实现：

• 使用C++ pair ，判断Uni-value subtree和累计值放到一起返回。

``````
/**
* Definition of TreeNode:
* class TreeNode {
* public:
*     int val;
*     TreeNode *left, *right;
*     TreeNode(int val) {
*         this->val = val;
*         this->left = this->right = NULL;
*     }
* }
*/

class Solution {
public:
/**
* @param root: the given tree
* @return: the number of uni-value subtrees.
*/
int countUnivalSubtrees(TreeNode * root) {
pair<int, bool> re = helperCount(root);
return re.first;

}
pair<int,bool> helperCount(TreeNode *root) {
pair<int, bool> res = {0, true};
if (root == nullptr) {
return res;
}
pair<int, bool> left, right;

left = helperCount(root->left);
right = helperCount(root->right);
if (!left.second || !right.second){
res.second = false;
}
if (root->left !=nullptr && root->left->val != root->val ){
res.second = false;
}
if (root->right !=nullptr && root->right->val != root->val ){
res.second = false;
}
if (res.second){
res = {left.first+right.first+1, true};
}
else {
res = {left.first+right.first, false};
}
return res;

}
};``````