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
- A post-order DFS returns whether the subtree rooted at a node is uni-value.
- A node qualifies when both children's subtrees are uni-value and each child's value equals the node's value.
- Count each qualifying node.
- 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
Trueso 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.