250. Count Univalue Subtrees - cocoder39/coco39_LC GitHub Wiki

250. Count Univalue Subtrees

is a subtree rooted with this node a unival tree? if so, increase by 1. hard to represent both isUnival and cnt through return value of helper(). (you can use -1 to represent un-isUnival, however -1 would hind the information that how many isUnival exist)

dfs: O(n) time and O(height) space

class Solution {
public:
    int countUnivalSubtrees(TreeNode* root) {
        int res = 0;
        isUnival(root, res);
        return res;
    }
private:
    bool isUnival(TreeNode* root, int& res) {
        if (! root) {
            return true;
        }
        
        bool left = isUnival(root->left, res);
        bool right = isUnival(root->right, res);
        
        if (left && right) {
            if ((! root->left || root->val == root->left->val) && (! root->right || root->val == root->right->val)) {
                res++;
                return true;
            }
        }
        return false;
    }
};

Pay attentation to the difference between

bool left = isUnival(root->left);
bool right = isUnival(root->right);
if (left && right) {
        }

and

if (isUnival(root->left) && isUnival(root->right)) {
}