[leetcode] 250. Count Univalue Subtrees解題レポート
タイトルリンク:https://leetcode.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.
For example: Given binary tree,
return
構想:ノードの左サブツリーと右サブツリーの値が等しい場合、カウント+1.したがって、1つのノードが出発する、すべてのノードが等しいか否かを再帰的に判定するだけでよい.葉の結点も一つの結果だ.
コードは次のとおりです.
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
. 構想:ノードの左サブツリーと右サブツリーの値が等しい場合、カウント+1.したがって、1つのノードが出発する、すべてのノードが等しいか否かを再帰的に判定するだけでよい.葉の結点も一つの結果だ.
コードは次のとおりです.
/**
* 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:
bool DFS(TreeNode* root, int pre, int& ans)
{
if(!root) return true;
bool flag1 = DFS(root->left, root->val, ans);
bool flag2 = DFS(root->right, root->val, ans);
if(flag1 && flag2) ans++;
return (root->val == pre) && flag1 && flag2;
}
int countUnivalSubtrees(TreeNode* root) {
if(!root) return 0;
int ans = 0;
DFS(root, root->val, ans);
return ans;
}
};