2196. Create Binary Tree From Descriptions

2196. Create Binary Tree From Descriptionsopen in new window

🟠 🔖 树 深度优先搜索 广度优先搜索 数组 哈希表 二叉树 🔗 LeetCodeopen in new window

题目

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 的描述来构造二叉树并返回其根节点。

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

解题思路

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

首先，创建一个空字典 map，用于存储树节点，键为节点的值，值为对应的节点对象 TreeNode。
遍历描述数组 descriptions，对于每个描述 [parent, child, isLeft]：
- 如果 parent 不在 map 中，创建一个值为 parent 的树节点，并将其加入 map。
- 如果 child 不在 map 中，创建一个值为 child 的树节点，并将其加入 map。
将所有节点的值存入 set 中，因为根节点没有父节点，所以可以通过排除所有有父节点的元素，找到根节点。
再次遍历描述数组，对于每个描述 [parent, child, isLeft]：

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

最后，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]);
};

2196. Create Binary Tree From Descriptions

# 2196. Create Binary Tree From Descriptionsopen in new window

# 题目

# 题目大意

# 解题思路

# 代码

# 相关题目

2196. Create Binary Tree From Descriptionsopen in new window

题目

题目大意

解题思路

代码

相关题目