Given the root
of a binary tree, return the number of uni-value subtrees.
A uni-value subtree means all nodes of the subtree have the same value.
Example 1:
Input: root = [5,1,5,5,5,null,5] Output: 4
Example 2:
Input: root = [] Output: 0
Example 3:
Input: root = [5,5,5,5,5,null,5] Output: 6
Constraints:
- The numbrt of the node in the tree will be in the range
[0, 1000]
. -1000 <= Node.val <= 1000
递归
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int countUnivalSubtrees(TreeNode* root) { int res = 0; helper(root, res); return res; } private: bool helper(TreeNode* root, int & res){ // return whether root is univalue if(not root) return true; bool isLeft = helper(root->left, res); bool isRight = helper(root->right, res); if(isLeft && isRight && ( !root->left || root->val == root->left->val ) && ( !root->right || root->val == root->right->val )){ res++; return true; } return false; } };
Mistakes:
No comments:
Post a Comment