NeetCode #416LC-2196MediumTrees
← Back to All Problems#416 · #2196 · Create Binary Tree From Descriptions(根据描述创建二叉树)
📌 Problem Statement & Constraints
You are given a 2D array
descriptions where descriptions[i] = [parent, child, isLeft] describes a binary tree edge. Return the root of the reconstructed tree. All node values are unique and the input describes a valid binary tree. Constraints: 1 <= descriptions.length <= 10^4, 1 <= parent, child <= 10^5.💡 Core Algorithmic Approaches
- Create or reuse a node for every value mentioned, then link each child to its parent on the correct side.
- The root is the only value that never appears as a child.
- A dictionary from value to node makes the create-or-reuse step O(1).
- Then scan for the value absent from the children set.
💻 Benchmark Python3 Implementation
class Solution:
def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:
nodes = {}
children = set()
for p, c, is_left in descriptions:
if p not in nodes:
nodes[p] = TreeNode(p)
if c not in nodes:
nodes[c] = TreeNode(c)
if is_left:
nodes[p].left = nodes[c]
else:
nodes[p].right = nodes[c]
children.add(c)
for v, node in nodes.items():
if v not in children: # never a child -> the root
return node
return None⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): one pass to build, one to find the root.
💾 Space Complexity
O(n) for the node map and the children set.
⚠️ Interview Pitfalls & Follow-ups
- Creating a new node for every mention: a value can appear as both a parent and a child, so the map must be checked first.
- Assuming the descriptions are topologically ordered: they are not; a child may be described before its parent.
- Swapping
leftandright:isLeft == 1means left,0means right. - Looking for the root by value ordering: the root is identified structurally (never a child), not by value.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.