Count Univalue Subtrees - Leetcode Solution

Problem description: 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

Solution: To solve this problem, we need to solve it recursively. At each node, we will check if its left and right children are uni-valued subtrees or not. If they are, we will check if the value of the current node is equal to the value of its children. If yes, then we can say that the current node is also a uni-valued subtree. Otherwise, it's not. We will return this info to the parent node.

We will use a variable count to keep track of the number of uni-valued subtrees. Initially, we set it to 0. At each node, if it's a uni-valued subtree, we increment count by 1.

The base case for recursion is when the current node is null. In that case, we return true, meaning it's a uni-valued subtree.

Here's the Python code:

def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int: self.count = 0

def isUnival(node):
    if node is None:
        return True
    
    left = isUnival(node.left)
    right = isUnival(node.right)
    
    if left and right:
        if node.left and node.left.val != node.val:
            return False
        if node.right and node.right.val != node.val:
            return False
        self.count += 1  # current node is also a uni-valued subtree
        return True
    
    return False

isUnival(root)  # call the recursive function
return self.count

Time Complexity: O(n). Since we are visiting each node of the binary tree only once, the time complexity is O(n).

Space Complexity: O(h). The space used by the recursion stack is equal to the height of the binary tree, which is at most O(n) for a skewed tree and O(log n) for a balanced tree.

1