Wednesday, August 5, 2015

LeetCode [250] Count Univalue Subtrees

 250. Count Univalue Subtrees

Medium

Given the root of a binary tree, return the number of uni-value subtrees.

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//C++: 4ms
/**
 * 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) {
        int cnt = 0;
        helper(root, cnt);
        return cnt;
    }
    bool helper(TreeNode* root, int &cnt){
        if(!root) return true;
        bool left = helper(root->left, cnt);
        bool right = helper(root->right, cnt);
        if(!left || !right) return false;
        if(root->left && root->left->val!=root->val) return false;
        if(root->right && root->right->val!=root->val) return false;
        cnt++;
        return true;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int ret = 0;
    public int countUnivalSubtrees(TreeNode root) {
        isUni(root);
        return ret;
    }
    
    boolean isUni(TreeNode root){
        if (root==null) return true;
        boolean left = isUni(root.left);
        boolean right = isUni(root.right);
        
        int v = root.val;
        if(!left || !right) return false;
        if(root.left!=null && root.left.val!=v) return false;
        if(root.right!=null && root.right.val!=v) return false;
        ret ++;
        return true;
    }
}

No comments:

Post a Comment