Concise and clear C++ easy to understand solution


  • 0
    Q

    A tree is universal has two steps:

    1. the left subtree is universal and the right subtree is uni-value.
    2. root value is same as right child(if exists) and left child(if exists)

    DFS method. Using count to store the # of current uni-value. The boolean helper() function returns whether the current tree is uni-value.

    int countUnivalSubtrees(TreeNode* root) {
        if (!root) return 0;
        
        int cnt=0;
        helper(root, cnt);
        return cnt;
    }
    
    bool helper(TreeNode* root, int& cnt) {
        if (!root) return true;
        
        bool isLeft = helper(root->left, cnt);
        bool isRight = helper(root->right, cnt);
        bool tmp1 = root->left? root->val==root->left->val : true;
        bool tmp2 = root->right? root->val==root->right->val : true;
        bool isRoot = isLeft && isRight && tmp1 && tmp2;
        
        if (isRoot) cnt++;
        return isRoot;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.