Solution Explanation: Count Univalue Subtrees

This problem asks us to count the number of univalue subtrees within a given binary tree. A univalue subtree is a subtree where all nodes have the same value. The solution uses a depth-first search (DFS) approach.

Approach

The core idea is to recursively traverse the tree. For each node, we check if its left and right subtrees are univalue and if the node's value matches the values in its subtrees. If all these conditions are true, the subtree rooted at the current node is univalue, and we increment the counter.

The recursive function dfs returns true if the subtree rooted at the current node is univalue, and false otherwise. This boolean result is crucial for efficiently propagating the univalue status up the tree.

Time and Space Complexity Analysis

• Time Complexity: O(N), where N is the number of nodes in the binary tree. We visit each node exactly once during the DFS traversal.

• Space Complexity: O(H), where H is the height of the binary tree. This space is used by the recursive call stack. In the worst case (a skewed tree), H can be equal to N. In the best case (a balanced tree), H is log₂N.

Code Explanation (Python as an example, but the logic applies to all languages)

class Solution:
    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:
        self.count = 0  # Initialize the univalue subtree count
 
        def dfs(node):
            # Base case: Empty subtree is a univalue subtree (trivially)
            if not node:
                return True
 
            # Recursively check left and right subtrees
            left_unival = dfs(node.left)
            right_unival = dfs(node.right)
 
            # Check if current node's value matches left and right subtree values
            is_unival = True
            if node.left and node.left.val != node.val:
                is_unival = False
            if node.right and node.right.val != node.val:
                is_unival = False
 
            # If current node is univalue and its children are univalue subtrees, increment count
            if is_unival and left_unival and right_unival:
                self.count += 1
 
            # Return whether the current subtree is univalue
            return is_unival
 
        dfs(root)
        return self.count

The dfs function works as follows:

1. Base Case: If the node is None (empty subtree), it's considered a univalue subtree, so True is returned.

2. Recursive Calls: Recursively checks the left and right subtrees using dfs.

3. Univalue Check: Checks if the current node's value is consistent with its children's values. If any child has a different value, is_unival becomes False.

4. Count Update: If is_unival is True (current node is consistent with its children), and both children are univalue subtrees (left_unival and right_unival are True), then the subtree rooted at the current node is univalue, and the count is incremented.

5. Return Value: The function returns is_unival, indicating whether the current subtree is univalue. This allows the parent nodes to determine their univalue status based on their children's status.

The provided code in other languages (Java, C++, Go, TypeScript, JavaScript) follows the same fundamental logic, differing only in syntax and data structure representations. The core recursive DFS strategy and univalue checking remain consistent across all implementations.