Tuesday, December 29, 2015

250. Count Univalue Subtrees ---M

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
A:
递归

/**
 * 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