Count Univalue Subtrees Solutions in C++

/// Source : https://leetcode.com/problems/count-univalue-subtrees/description/
/// Author : liuyubobobo
/// Time   : 2018-06-02

#include <iostream>

using namespace std;


/// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

/// Recursive
/// Time Complexity: O(n^2)
/// Space Complexty: O(h)
class Solution {
public:
    int countUnivalSubtrees(TreeNode* root) {

        if(root == NULL)
            return 0;

        int res = 0;
        if(root->left != NULL)
            res += countUnivalSubtrees(root->left);

        if(root->right != NULL)
            res += countUnivalSubtrees(root->right);

        if(isUnivalTree(root, root->val))
            res += 1;

        return res;
    }

private:
    bool isUnivalTree(TreeNode* root, int val){

        if(root == NULL)
            return true;

        if(root->val != val)
            return false;

        return isUnivalTree(root->left, val) && isUnivalTree(root->right, val);
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/count-univalue-subtrees/description/
/// Author : liuyubobobo
/// Time   : 2018-06-02

#include <iostream>

using namespace std;


/// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

/// Recursive
/// Time Complexity: O(n)
/// Space Complexty: O(h)
class Solution {
public:
    int countUnivalSubtrees(TreeNode* root) {

        if(root == NULL)
            return 0;

        return dfs(root).second;
    }

private:
    pair<bool, int> dfs(TreeNode* root){

        pair<bool, int> leftRes, rightRes;
        int res = 0;
        bool isUnivalTree = true;

        if(root->left != NULL) {
            leftRes = dfs(root->left);
            res += leftRes.second;
            isUnivalTree = isUnivalTree && leftRes.first && root->val == root->left->val;
        }

        if(root->right != NULL) {
            rightRes = dfs(root->right);
            res += rightRes.second;
            isUnivalTree = isUnivalTree && rightRes.first && root->val == root->right->val;
        }

        if(isUnivalTree)
            res += 1;

        return make_pair(isUnivalTree, res);
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/count-univalue-subtrees/description/
/// Author : liuyubobobo
/// Time   : 2018-06-02

#include <iostream>

using namespace std;


/// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

/// Recursive
/// Use class variable to store the result
/// Time Complexity: O(n)
/// Space Complexty: O(h)
class Solution {

private:
    int result = 0;

public:
    int countUnivalSubtrees(TreeNode* root) {

        if(root) dfs(root);
        return result;
    }

private:
    bool dfs(TreeNode* node){

        bool ok = true;
        if(node->left){
            bool isLeft = dfs(node->left);
            if(!isLeft || node->val != node->left->val) ok = false;
        }

        if(node->right){
            bool isRight = dfs(node->right);
            if(!isRight || node->val != node->right->val) ok = false;
        }

        if(ok) result ++;
        return ok;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/count-univalue-subtrees/description/
/// Author : liuyubobobo
/// Time   : 2019-03-02

#include <iostream>

using namespace std;


/// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

/// Recursive
/// Treat null as univalue subtree and make the implementation much more concise :-)
///
/// Time Complexity: O(n)
/// Space Complexty: O(h)
class Solution {

private:
    int result = 0;

public:
    int countUnivalSubtrees(TreeNode* root) {

        dfs(root);
        return result;
    }

private:
    bool dfs(TreeNode* node){

        if(!node) return true;

        bool isLeft = dfs(node->left), isRight = dfs(node->right);
        bool ok = isLeft && (!node->left || node->val == node->left->val) &&
                  isRight && (!node->right || node->val == node->right->val);

        if(ok) result ++;
        return ok;
    }
};


int main() {

//      5
//     / \
//    1  5
//   / \  \
//  5  5  5
    TreeNode *root = new TreeNode(5);
    root->left = new TreeNode(1);
    root->right = new TreeNode(5);
    root->left->left = new TreeNode(5);
    root->left->right = new TreeNode(5);
    root->right->right = new TreeNode(5);
    cout << Solution().countUnivalSubtrees(root) << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/count-univalue-subtrees/description/
/// Author : liuyubobobo
/// Time   : 2019-03-03

#include <iostream>

using namespace std;


/// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

/// Recursive
/// Pass parent value to make the implementation even more concise :-)
///
/// Time Complexity: O(n)
/// Space Complexty: O(h)
class Solution {

private:
    int result = 0;

public:
    int countUnivalSubtrees(TreeNode* root) {

        dfs(root, NULL);
        return result;
    }

private:
    bool dfs(TreeNode* node, TreeNode* parent){

        if(!node) return true;

        bool isLeft = dfs(node->left, node), isRight = dfs(node->right, node);
        if(!isLeft || !isRight) return false;

        result ++;
        return parent && node->val == parent->val;
    }
};


int main() {

//      5
//     / \
//    1  5
//   / \  \
//  5  5  5
    TreeNode *root = new TreeNode(5);
    root->left = new TreeNode(1);
    root->right = new TreeNode(5);
    root->left->left = new TreeNode(5);
    root->left->right = new TreeNode(5);
    root->right->right = new TreeNode(5);
    cout << Solution().countUnivalSubtrees(root) << endl;

    return 0;
}