2196. 根据描述创建二叉树

🟠   🔖  树 数组 哈希表 二叉树  🔗 力扣 LeetCode

题目

You are given a 2D integer array descriptions where descriptions[i] = [parenti, childi, isLefti] indicates that parenti is the parent of childi in a binary tree of unique values. Furthermore,

• If isLefti == 1, then childi is the left child of parenti.
• If isLefti == 0, then childi is the right child of parenti.

Construct the binary tree described by descriptions and return its root.

The test cases will be generated such that the binary tree is valid.

Example 1:

Input: descriptions = [[20,15,1],[20,17,0],[50,20,1],[50,80,0],[80,19,1]]

Output: [50,20,80,15,17,19]

Explanation: The root node is the node with value 50 since it has no parent.

The resulting binary tree is shown in the diagram.

Example 2:

Input: descriptions = [[1,2,1],[2,3,0],[3,4,1]]

Output: [1,2,null,null,3,4]

Explanation: The root node is the node with value 1 since it has no parent.

The resulting binary tree is shown in the diagram.

Constraints:

• 1 <= descriptions.length <= 10^4
• descriptions[i].length == 3
• 1 <= parenti, childi <= 10^5
• 0 <= isLefti <= 1
• The binary tree described by descriptions is valid.

题目大意

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

• 如果 isLefti == 1 ，那么 childi 就是 parenti 的左子节点。
• 如果 isLefti == 0 ，那么 childi 就是 parenti 的右子节点。 请你根据 descriptions 的描述来构造二叉树并返回其 根节点 。

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

解题思路

这道题可以通过字典来存储树节点，然后根据描述构建二叉树。

1. 首先，创建一个空字典 map，用于存储树节点，键为节点的值，值为对应的节点对象 TreeNode。

2. 遍历描述数组 descriptions，对于每个描述 [parent, child, isLeft]：

   • 如果 parent 不在 map 中，创建一个值为 parent 的树节点，并将其加入 map。
   • 如果 child 不在 map 中，创建一个值为 child 的树节点，并将其加入 map。

3. 将所有节点的值存入 set 中，因为根节点没有父节点，所以可以通过排除所有有父节点的元素，找到根节点。

4. 再次遍历描述数组，对于每个描述 [parent, child, isLeft]：

• 通过 map 取得对应的父节点和子节点对象。
• 根据 isLeft 的值判断，如果为 1，则将子节点作为左孩子加到父节点上；如果为 0，则将子节点作为右孩子加到父节点上。
• 删除 set 中 child 对应的值。

5. 最后，set 中剩下的值即为根节点，在 map 中找到对应的节点对象返回，即为构建好的二叉树的根。

代码

/**
 * @param {number[][]} descriptions
 * @return {TreeNode}
 */
var createBinaryTree = function (descriptions) {
	let map = new Map();
	for (let [parent, child, isLeft] of descriptions) {
		if (!map.has[parent]) map.set(parent, new TreeNode(parent));
		if (!map.has[child]) map.set(child, new TreeNode(child));
	}
	let set = new Set([...map.keys()]);
	for (let [parent, child, isLeft] of descriptions) {
		let node = map.get(parent);
		if (isLeft) node.left = map.get(child);
		else node.right = map.get(child);
		map.set(parent, node);
		set.delete(child);
	}
	return map.get([...set][0]);
};

相关题目

题号	标题	题解	标签	难度
109	有序链表转换二叉搜索树	[✓]	树 二叉搜索树 链表 2+
1719	重构一棵树的方案数		树 图