⚡Flashcard Drill➔
NeetCode #402LC-250MediumTreesNC Algo100
← Back to All Problems

#402 · #250 · Count Univalue Subtrees(统计同值子树)

📌 Problem Statement & Constraints

Given the root of a binary tree, return the number of uni-value subtrees: subtrees in which every node has the same value. Constraints: the number of nodes is in [0, 1000], -1000 <= Node.val <= 1000.

💡 Core Algorithmic Approaches

  1. A post-order DFS returns whether the subtree rooted at a node is uni-value.
  2. A node qualifies when both children's subtrees are uni-value and each child's value equals the node's value.
  3. Count each qualifying node.
  4. Leaves are always uni-value, which is the natural base case.

💻 Benchmark Python3 Implementation

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

        def is_uni(node: Optional[TreeNode]) -> bool:
            if not node:
                return True                # an empty subtree is trivially uni-value
            l = is_uni(node.left)
            r = is_uni(node.right)
            if not (l and r):
                return False               # a child subtree already failed
            if node.left and node.left.val != node.val:
                return False
            if node.right and node.right.val != node.val:
                return False
            self.cnt += 1                  # this subtree is uni-value
            return True

        is_uni(root)
        return self.cnt

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): each node is visited once.
💾 Space Complexity
O(h) for the recursion stack.

⚠️ Interview Pitfalls & Follow-ups

  • Counting before verifying the children: a node could be counted even though a descendant differs.
  • Comparing only the immediate children's values without their subtree status: both conditions are required.
  • Treating an empty subtree as non-uni-value: it must return True so that a single-child node can still qualify.
  • Using a global counter that is not reset: reset it per call.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Trees Problems