NeetCode #458LC-1361MediumTrees
← Back to All Problems#458 · #1361 · Validate Binary Tree Nodes(验证二叉树)
📌 Problem Statement & Constraints
You have
n binary tree nodes numbered 0..n-1, given leftChild and rightChild arrays where -1 means no child. Return true if they form exactly one valid binary tree. Constraints: 1 <= n <= 10^4, leftChild.length == rightChild.length == n.💡 Core Algorithmic Approaches
- A valid binary tree requires exactly one root (a node with no parent) and every other node to have exactly one parent.
- First verify parent uniqueness while counting roots: a node with two parents immediately fails.
- Then traverse from the unique root and check that all
nnodes are reachable -- this catches cycles and disconnected components. - The reachability check is what rules out a structure like a cycle with an extra dangling node.
💻 Benchmark Python3 Implementation
class Solution:
def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
from collections import deque
has_parent = [False] * n
for i in range(n):
for c in (leftChild[i], rightChild[i]):
if c != -1:
if has_parent[c]:
return False # a node has two parents
has_parent[c] = True
roots = [i for i in range(n) if not has_parent[i]]
if len(roots) != 1:
return False # zero or multiple roots
# traverse from the root and check full reachability
seen = set()
q = deque([roots[0]])
while q:
node = q.popleft()
if node in seen:
return False # cycle
seen.add(node)
for c in (leftChild[node], rightChild[node]):
if c != -1:
q.append(c)
return len(seen) == n # all nodes connected⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): one pass to check parents, one traversal.
💾 Space Complexity
O(n) for the bookkeeping arrays.
⚠️ Interview Pitfalls & Follow-ups
- Only checking the root count: a graph can have one root and still contain a cycle elsewhere.
- Skipping the reachability check: disconnected components would pass the parent test.
- Forgetting the two-parent check: a node reached from two parents makes the structure a DAG, not a tree.
- Assuming node 0 is the root: it need not be.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.