C++ one-pass recursive solution


  • 9
    X

    It was important for me to realize that: (a) when determining whether a subtree is univalue or not, we don't have to store the value it might be univalue with, since it's already stored at its root, so just the bool indicator is enough; (b) the counter has better to be stored separately from the recursion stack, and used as an accumulator rather than a return value we'd later sum between left and right subtrees.

    So the considerations above led to the following transparent solution:

       class Solution {
        public:
            int countUnivalSubtrees(TreeNode* root) {
                int count = 0;
                countUnivalSubtreesRecursive(root, count);
                return count;
            }
            
            bool countUnivalSubtreesRecursive(TreeNode* root, int& count)
            {
                if(root == NULL) return true;
                
                auto isLeftUnival = countUnivalSubtreesRecursive(root->left, count);
                auto isRightUnival = countUnivalSubtreesRecursive(root->right, count);
                
                if(isLeftUnival && isRightUnival
                    && ((root->left == NULL) || root->left->val == root->val)
                    && ((root->right == NULL) || root->right->val == root->val)
                )
                {
                    ++count;
                    return true;
                }
                return false;
            }
        };

  • 1
    S

    Thank you for the nice idea. I have the same idea, slightly different implementation.

    class Solution {
        int count = 0;
        bool is_univalue(TreeNode* root) {
            bool is_left = true, is_right = true;
            
            if (root->left != NULL) {
                is_left = is_univalue(root->left) && (root->val == root->left->val);
            }
            if (root->right != NULL)    {
                is_right = is_univalue(root->right) && (root->val == root->right->val);
            }
            
            if (is_left && is_right)    {
                count += 1;
                return true;
            } else  {
                return false;
            }
        }
        
    public:
        int countUnivalSubtrees(TreeNode* root) {
            if (root == NULL)   {
                return 0;
            }
            
            is_univalue(root);
            return count;
        }
    };
    

  • 0
    W
    This post is deleted!

  • 0
    B

    Thanks for your explanation, esp. the first point


Log in to reply
 

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