250. 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

// This includes duplicate calculation (Preorder Traversal)
int res = 0;
bool isUnival(TreeNode* node, int target) {
    if (!node) return true;
    return node->val == target && isUnival(node->left, target) && isUnival(node->right, target);
}
int countUnivalSubtrees(TreeNode* root) { // time: O(n^2); space: O(n)
    if (!root) return res;
    if (isUnival(root, root->val)) ++res;
    countUnivalSubtrees(root->left);
    countUnivalSubtrees(root->right);
    return res;
}

// Postorder Traversal
bool helper(TreeNode* node, int val, int& res) {
    if (!node) return true;
    bool left = helper(node->left, node->val, res);
    bool right = helper(node->right, node->val, res);
    if (!left || !right) return false;
    ++res;
    return node->val == val;
}
int countUnivalSubtrees(TreeNode* root) { // time: O(n); space: O(n)
    int res = 0;
    helper(root, -1, res);
    return res;
}

// This method only traverses all nodes once (Postorder Traversal)
bool helper(TreeNode* node, int& res) {
    if (!node) return true;
    bool left = helper(node->left, res); // whether the left subtree is univalue
    bool right = helper(node->right, res); // whether the right subtree is univalue
    if (left && right && 
        (!node->left || node->left->val == node->val) && 
        (!node->right || node->right->val == node->val)) {
        ++res;
        return true;
    } else 
        return false;
}
int countUnivalSubtrees(TreeNode* root) { // time: O(n); space: O(n)
    int res = 0;
    helper(root, res);
    return res;
}