2196. Create Binary Tree From Descriptions

Leetcode link

解题思路

本题要求我们根据题目给定的描述信息，构造一个二叉树

入参是一个数组 descriptions，其中每一项包含了三个信息：

• parent：标识当前元素的父元素
• child：标识当前元素的 value
• isLeft：标识当前元素是否是父元素的左节点

最后题目要求我们返回二叉树的根结点

通过观察题目给到的测试 case，我们不难发现题目给到的节点其实是乱序的

那么我们就需要维护一个 map 的映射，保证我们能够找到之前创建的节点

其次，我们还需要解决一个问题：如何找到跟节点

通过观察测试 case，我们可以得到一个结论：跟节点永远不会出现在 child 的位置上

我们可以通过这一点，维护一个 childNode Set，用来保存出现在 child 位置上的节点，最后遍历找出没在 Set 中的节点就是根结点

解决了这两个难点后，我们就可以开始遍历 descriptions 了，遍历过程中我们只需要做好四件事：

1. 判断父节点有没有被创建过，没有的话创建一个父节点，并将其保存到 map 中
2. 判断子节点有没有被创建过，没有的话创建一个子节点，并将其保存到 map 中
3. 建立父子节点之间的关系
4. 把子节点保存到 set 中

最后，我们遍历 map 然后找到没有在 set 中的节点返回就行～

Javascript

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[][]} descriptions
 * @return {TreeNode}
 */
var createBinaryTree = function (descriptions) {
  const childNode = new Set();
  const createdNode = new Map();
  for (const node of descriptions) {
    // 处理子节点
    let curNode
    if (createdNode.has(node[1])) {
      curNode = createdNode.get(node[1]);
    } else {
      curNode = new TreeNode(node[1]);
      createdNode.set(node[1], curNode);
    }
    // 处理父节点
    let parentNode
    if (createdNode.has(node[0])) {
      parentNode = createdNode.get(node[0]);
    } else {
      parentNode = new TreeNode(node[0]);
      createdNode.set(node[0], parentNode);
    }
    // 建立父子节点之间关系
    if (node[2]) {
      parentNode.left = curNode;
    } else {
      parentNode.right = curNode;
    }
    // 记录子节点
    childNode.add(node[1]);
  }
  // 找出根节点返回
  for (const [key, value] of createdNode) {
    if (!childNode.has(key)) {
      return value;
    }
  }
};

function TreeNode(val, left, right) {
    this.val = (val === undefined ? 0 : val)
    this.left = (left === undefined ? null : left)
    this.right = (right === undefined ? null : right)
}