Count Univalue Subtrees

class Solution {
public:
    pair<bool, int> traverse(TreeNode* root) {
        if (!root) {
            return {true, 0};
        }

        auto leftResult = traverse(root->left);
        auto rightResult = traverse(root->right);
        bool isLeftUnival = leftResult.first;
        bool isRightUnival = rightResult.first;
        int totalUnivals = leftResult.second + rightResult.second;

        // Check if both left and right are unival subtrees and match current node's value
        if (isLeftUnival && isRightUnival) {
            if (root->left && root->val != root->left->val) {
                return {false, totalUnivals};
            }
            if (root->right && root->val != root->right->val) {
                return {false, totalUnivals};
            }
            return {true, totalUnivals + 1};
        }

        // If either left or right is not a unival subtree
        return {false, totalUnivals};
    }

    int countUnivalSubtrees(TreeNode* root) {
        return traverse(root).second;
    }
};

This solution focuses on counting the number of univalue subtrees within a binary tree. A univalue subtree is defined as one where all the nodes have the same value.

The provided C++ implementation uses a recursive approach. The primary function countUnivalSubtrees initiates the process by calling the helper function traverse, which navigates through the tree.

• The traverse function forms the core of the solution:
  • It accepts a pointer to the root of a subtree and returns a pair of a boolean and an integer. The boolean indicates whether the current subtree is univalue, and the integer represents the count of univalue subtrees within it.
  • If the current node is null, it immediately returns a pair {true, 0}, implying that a null subtree is univalue and has zero univalue subtrees.
  • It then recursively assesses both left and right children of the current node, collecting results about their univalue status and count.
  • It validates whether both left and right subtrees are univalue and ensures that if they have values, these values match the current node's value.
  • If both conditions are satisfied, it recognizes the entire subtree rooted at the current node as univalue and increments the count.
  • If either subtree is not univalue, it simply returns the combined count from both subtrees without incrementing it.

The result from traverse provides the total count of univalue subtrees which countUnivalSubtrees returns as the final result.

This method effectively combines recursion with decision logic based on tree properties to solve the problem efficiently.

class Solution {
    private Pair<Boolean, Integer> traverse(TreeNode node) {
        if (node == null) {
            return new Pair<>(true, 0);
        }
        
        Pair<Boolean, Integer> leftResult = traverse(node.left);
        Pair<Boolean, Integer> rightResult = traverse(node.right);
        boolean isLeftUnival = leftResult.getKey();
        boolean isRightUnival = rightResult.getKey();
        int totalCount = leftResult.getValue() + rightResult.getValue();
        
        if (isLeftUnival && isRightUnival) {
            if (node.left != null && node.val != node.left.val) {
                return new Pair<>(false, totalCount);
            }
            if (node.right != null && node.val != node.right.val) {
                return new Pair<>(false, totalCount);
            }
            totalCount++;
            return new Pair<>(true, totalCount);
        }
        return new Pair<>(false, totalCount);
    }
    
    public int countUnivalSubtrees(TreeNode root) {
        return traverse(root).getValue();
    }
}

This Java solution addresses the problem of counting univalue (uniform value) subtrees within a binary tree. Each subtree, where all nodes have the same value, is considered a univalue subtree.

Here's an overview of how the solution operates:

• Define a helper function traverse that uses recursive DFS (depth-first search) to explore each node in the tree starting from the root. It returns a pair of values, where the first part of the pair is a boolean indicating whether the subtree is univalue, and the second part is the count of univalue subtrees beneath the current node.

• In the traverse function:

  • Check if node is null. If it is, return a pair of true and 0 because a null tree is trivially univalue and has no subtrees.
  • Recursively gather results from the left and right subtree of the current node.
  • Check if both left and right subtrees are univalue. Additional checks ensure that if the left or right node exists, they must match the current node’s value for the current subtree to be univalue.
  • Aggregate results, and if all conditions for a univalue subtree are met, increment the count.

• In the countUnivalSubtrees method, call the traverse function on the root and retrieve the subtree count from the result.

This approach efficiently determines the count of univalue subtrees by evaluating and merging results through postorder traversal, ensuring that each tree node is visited in a depth-first manner. The use of a Pair object simplifies returning multiple values from the recursive calls.

class Solution:
    def countSingleValueSubtrees(self, root: Optional[TreeNode]) -> int:
        def check_univalue(subroot):
            if subroot is None:
                return True, 0
                
            left_result = check_univalue(subroot.left)
            right_result = check_univalue(subroot.right)
            left_univalue = left_result[0]
            right_univalue = right_result[0]
            total_count = left_result[1] + right_result[1]

            if left_univalue and right_univalue:
                if subroot.left and subroot.val != subroot.left.val:
                    return False, total_count
                if subroot.right and subroot.val != subroot.right.val:
                    return False, total_count

                return True, total_count + 1

            return False, total_count
        
        return check_univalue(root)[1]

This solution addresses the problem of counting univalue subtrees within a binary tree. The countSingleValueSubtrees function within the Solution class implements this functionality. Here's how the code works:

• A helper function check_univalue is defined within countSingleValueSubtrees. It takes subroot as an argument, representing the current node in the tree.

• First, it checks if the subroot is None. If true, it returns that the subtree is univalue and there are no subtrees, i.e., (True, 0).

• It then recursively calls itself for the left and right children of the subroot, obtaining left_result and right_result. These calls provide a tuple containing a boolean if the subtree from this child is a univalue and the count of univalue subtrees in the respective subtrees.

• The left_univalue and right_univalue are the boolean values indicating whether the left and right subtrees are univalues, respectively, and total_count is the sum of univalue subtree counts from the left and right children.

• Using the obtained values, the code checks:

  • Both the left and right subtrees must be univalue.
  • If the current node has a left child, the value of this child must be the same as the current node.
  • The same rule applies for the right child.

• If all conditions are met, it concludes that the subtree rooted at subroot is also a univalue subtree, increments the total_count by 1, and marks the subtree as univalue.

• If any condition fails, it marks the subtree as not univalue and returns the current total count.

• The main function countSingleValueSubtrees starts the check from the root and returns the second element of the tuple returned by check_univalue(root) which represents the count of univalue subtrees in the entire tree.