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

``````class Solution {
public:
int res = 0;
int countUnivalSubtrees(TreeNode* root) {
if (!root) return res;
if (isUnival(root, root->val)) ++res;
countUnivalSubtrees(root->left);
countUnivalSubtrees(root->right);
return res;
}
bool isUnival(TreeNode *root, int val) {
if (!root) return true;
return root->val == val && isUnival(root->left, val) && isUnival(root->right, val);
}
};
``````

``````class Solution {
public:
int countUnivalSubtrees(TreeNode* root) {
int res = 0;
isUnival(root, -1, res);
return res;
}
bool isUnival(TreeNode* root, int val, int& res) {
if (!root) return true;
if (!isUnival(root->left, root->val, res) | !isUnival(root->right, root->val, res)) {
return false;
}
++res;
return root->val == val;
}
};
``````

``````class Solution {
public:
int countUnivalSubtrees(TreeNode* root) {
bool b = true;
return isUnival(root, b);
}
int isUnival(TreeNode *root, bool &b) {
if (!root) return 0;
bool l = true, r = true;
int res = isUnival(root->left, l) + isUnival(root->right, r);
b = l && r && (root->left ? root->val == root->left->val : true) && (root->right ? root->val == root->right->val : true);
return res + b;
}
};
``````

``````class Solution {
public:
int countUnivalSubtrees(TreeNode* root) {
if (!root) return 0;
unordered_set<TreeNode*> res;
stack<TreeNode*> st{{root}};
while (!st.empty()) {
TreeNode *t = st.top();
if ((!t->left && !t->right) || t->left == head || t->right == head) {
if (!t->left && !t->right) {
res.insert(t);
} else if (!t->left && res.find(t->right) != res.end() && t->right->val == t->val) {
res.insert(t);
} else if (!t->right && res.find(t->left) != res.end() && t->left->val == t->val) {
res.insert(t);
} else if (t->left && t->right && res.find(t->left) != res.end() && res.find(t->right) != res.end() && t->left->val == t->val && t->right->val == t->val) {
res.insert(t);
}
st.pop();
} else {
if (t->right) st.push(t->right);
if (t->left) st.push(t->left);
}
}
return res.size();
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/250

Subtree of Another Tree

Longest Univalue Path

Largest BST Subtree

Binary Tree Postorder Traversal

Same Tree

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

https://leetcode.com/problems/count-univalue-subtrees/discuss/67644/AC-clean-Java-solution

https://leetcode.com/problems/count-univalue-subtrees/discuss/67573/My-Concise-JAVA-Solution

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation