LeetCode – 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

实现：

• 创建判断相同值子树方法isUnivalSubtrees， 判断其左、右节点与父节点是否相同，判定为Uni-value subtree（比较子节点与父节点val值时要先判断下对应left， right是否为空）， 分别判断左子树和右子树的是否为Uni-value subtree， 如果是计数器累加。
• isUnivalSubtrees 时间 复杂度O(n) 嵌入 countUnivalSubtrees后 O(n^2)

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param root: the given tree
     * @return: the number of uni-value subtrees.
     */
    int countUnivalSubtrees(TreeNode * root) {
        int total = 0;
        if (root == nullptr){
            return 0;
        }
        total = countUnivalSubtrees(root->left) + countUnivalSubtrees(root->right);
        if (isUnivalSubtrees(root)){
            total +=1;
        }
        return total;
        
    }
private:
    bool isUnivalSubtrees(TreeNode * root){
        if (root == nullptr) {
            return true;
        }
        if (root->left!=nullptr && root->left->val != root->val) {
            return false;
        }
        if (root->right!=nullptr && root->right->val != root->val){
            return false;
        }
        if (isUnivalSubtrees(root->left) && isUnivalSubtrees(root->right)){
            return true;
        }
        return false;
    }
};

实现：

•  判断是否为Uni-value subtree的同时累计符合条件的子树数量，一起返回。
•  O(N)      

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param root: the given tree
     * @return: the number of uni-value subtrees.
     */
    int countUnivalSubtrees(TreeNode * root) {
        bool isUnival = true;
        return helperCount(root, isUnival);
        
    }
    int helperCount(TreeNode *root, bool& isUnival) {
        if (root == nullptr) {
            isUnival = true;
            return 0;
        }
        bool isLeftunival = true;
        bool isRightunival = true;
        int leftCount = 0;
        int rightCount = 0;
        leftCount = helperCount(root->left, isLeftunival);
        rightCount = helperCount(root->right, isRightunival);
        if (!isLeftunival || !isRightunival){
            isUnival = false;
        }
        if (root->left !=nullptr && root->left->val != root->val ){
            isUnival = false;
        }
        if (root->right !=nullptr && root->right->val != root->val ){
            isUnival = false;
        }
        if (isUnival){
            return leftCount+rightCount+1;
        }
        else {
            return leftCount+rightCount;
        }
        
    }
};

实现：

• 使用C++ pair ，判断Uni-value subtree和累计值放到一起返回。

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param root: the given tree
     * @return: the number of uni-value subtrees.
     */
    int countUnivalSubtrees(TreeNode * root) {
        pair<int, bool> re = helperCount(root);
        return re.first;
        
    }
    pair<int,bool> helperCount(TreeNode *root) {
        pair<int, bool> res = {0, true};
        if (root == nullptr) {
            return res;
        }
        pair<int, bool> left, right;
  
        left = helperCount(root->left);
        right = helperCount(root->right);
        if (!left.second || !right.second){
            res.second = false;
        }
        if (root->left !=nullptr && root->left->val != root->val ){
            res.second = false;
        }
        if (root->right !=nullptr && root->right->val != root->val ){
            res.second = false;
        }
        if (res.second){
            res = {left.first+right.first+1, true};
        }
        else {
            res = {left.first+right.first, false};
        }
        return res;
        
    }
};

参考及引用:

   https://www.youtube.com/watch?v=7HgsS8bRvjo