What is the primary approach for solving the Create Binary Tree From Descriptions problem?

The problem can be efficiently solved using array scanning and hash lookup to quickly identify parent-child relationships and reconstruct the tree.

How do I find the root node in the Create Binary Tree From Descriptions problem?

The root node is the one that does not appear as a child in any description. Track all child nodes and the missing one will be the root.

What is the time complexity of the solution for Create Binary Tree From Descriptions?

The time complexity is O(n), where n is the number of descriptions, as we process each description once to build the tree.

What is the space complexity of the Create Binary Tree From Descriptions solution?

The space complexity is O(n) because we store the nodes in a hash map and potentially in the resulting tree structure.

What should I focus on when solving the Create Binary Tree From Descriptions problem?

Focus on efficiently constructing the tree using hash lookups, correctly assigning children, and identifying the root node without excessive checks.

#2196

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

根据描述创建二叉树

给你一个二维整数数组 descriptions ，其中 descriptions[i] = [parent i , child i , isLeft i ] 表示 parent i 是 child i 在二叉树中的父节点，二叉树中各节点的值互不相同。此外：如果 isLeft i == …

数组哈希表树二叉树

题目描述

给你一个二维整数数组 descriptions ，其中 descriptions[i] = [parent_i, child_i, isLeft_i] 表示 parent_i 是 child_i 在 二叉树 中的 父节点，二叉树中各节点的值 互不相同 。此外：

如果 isLeft_i == 1 ，那么 child_i 就是 parent_i 的左子节点。
如果 isLeft_i == 0 ，那么 child_i 就是 parent_i 的右子节点。

请你根据 descriptions 的描述来构造二叉树并返回其 根节点 。

测试用例会保证可以构造出有效的二叉树。

示例 1：

输入：descriptions = [[20,15,1],[20,17,0],[50,20,1],[50,80,0],[80,19,1]]
输出：[50,20,80,15,17,19]
解释：根节点是值为 50 的节点，因为它没有父节点。
结果二叉树如上图所示。

示例 2：

输入：descriptions = [[1,2,1],[2,3,0],[3,4,1]]
输出：[1,2,null,null,3,4]
解释：根节点是值为 1 的节点，因为它没有父节点。 
结果二叉树如上图所示。

提示：

1 <= descriptions.length <= 10⁴
descriptions[i].length == 3
1 <= parent_i, child_i <= 10⁵
0 <= isLeft_i <= 1
descriptions 所描述的二叉树是一棵有效二叉树

lightbulb

解题思路

方法一：哈希表

我们可以用一个哈希表 $\textit{nodes}$ 来存储所有节点，其中键为节点的值，值为节点本身，用一个集合 $\textit{children}$ 来存储所有的子节点。

遍历 $\textit{descriptions}$ ，对于每个描述 $[\textit{parent}, \textit{child}, \textit{isLeft}]$ ，如果 $\textit{parent}$ 不在 $\textit{nodes}$ 中，我们就将 $\textit{parent}$ 加入 $\textit{nodes}$ ，并初始化一个值为 $\textit{parent}$ 的节点。如果 $\textit{child}$ 不在 $\textit{nodes}$ 中，我们就将 $\textit{child}$ 加入 $\textit{nodes}$ ，并初始化一个值为 $\textit{child}$ 的节点。然后我们将 $\textit{child}$ 加入 $\textit{children}$ 。

如果 $\textit{isLeft}$ 为真，我们就将 $\textit{child}$ 作为 $\textit{parent}$ 的左子节点，否则我们就将 $\textit{child}$ 作为 $\textit{parent}$ 的右子节点。

最后，我们遍历 $\textit{nodes}$ ，如果某个节点的值不在 $\textit{children}$ 中，那么这个节点就是根节点，我们返回这个节点。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是 $\textit{descriptions}$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:
        nodes = defaultdict(TreeNode)
        children = set()
        for parent, child, isLeft in descriptions:
            if parent not in nodes:
                nodes[parent] = TreeNode(parent)
            if child not in nodes:
                nodes[child] = TreeNode(child)
            children.add(child)
            if isLeft:
                nodes[parent].left = nodes[child]
            else:
                nodes[parent].right = nodes[child]
        root = (set(nodes.keys()) - children).pop()
        return nodes[root]

speed

复杂度分析

指标	值
时间	O(n)
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate handle efficient tree construction using hash maps?
question_mark
Does the candidate identify the root node correctly without extra checks?
question_mark
How well does the candidate optimize space and time complexity while solving the problem?

warning

常见陷阱

外企场景

error
Overcomplicating the identification of the root node, which should be straightforward by excluding children.
error
Not utilizing hash maps effectively, which can lead to inefficient lookups when constructing the tree.
error
Confusing left and right child assignments, especially if the index or flag is misinterpreted.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the tree had additional constraints, such as balanced or full binary trees?
arrow_right_alt
How would the solution change if the parent-child descriptions were in a different format?
arrow_right_alt
How can we optimize the space complexity if we were asked to process multiple trees simultaneously?

help

常见问题

外企场景

继续练习

#1110 删点成林 #2049 统计最高分的节点数目 #2368 受限条件下可到达节点的数目