250.Count Univalue Subtrees¶
Tags: Medium
Tree
Links: https://leetcode-cn.com/problems/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
/**
* 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) {
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
if (!root) return 0;
queue<TreeNode *> q;
q.push(root);
int cnt = 0;
while (!q.empty()) {
TreeNode *tmp = q.front(); q.pop();
//如果是叶节点,直接+1
if (!tmp -> left && !tmp -> right) {
++cnt;
}
else if (tmp -> left && tmp -> right) {
q.push(tmp -> left); q.push(tmp -> right);
int target = tmp -> val;
if (check(tmp -> left, target) && check(tmp -> right, target)) ++cnt;
}
else if (tmp -> left && !tmp -> right) {
q.push(tmp -> left);
if (check(tmp -> left, tmp -> val)) ++cnt;
}
else {
q.push(tmp -> right);
if (check(tmp -> right, tmp -> val)) ++cnt;
}
}
return cnt;
}
bool check(TreeNode *root, int target)
{
queue<TreeNode *> q;
q.push(root);
while (!q.empty()) {
TreeNode *tmp = q.front(); q.pop();
if (tmp -> val != target) return false;
if (tmp -> left) q.push(tmp -> left);
if (tmp -> right) q.push(tmp -> right);
}
return true;
}
};
思路是正确的,对每个节点去判断以此节点为根的子树的情况。注意对子树的理解,叶节点肯定可以满足,另外子树的值和根节点的值也必须相同。只不过上面的代码不够精简,所以先精简代码然后在优化。
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);
}
};