leetcode-105 从前序与中序遍历序列构造二叉树

/**
 * 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[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function (preorder, inorder) {
  // 前序 preorder
  // 中序 inorder
  // preorder的头节点就是root节点
  // 然后在inorder里面找到这个节点
  // 左边长度就是左子树个数
  // 右边长度就是右子树个数
  // preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
  if (!preorder.length) return null;
  const nodeValue = preorder[0];
  const root = new TreeNode(nodeValue);
  const idx = inorder.indexOf(nodeValue);

  const leftLen = idx === -1 ? 0 : idx;
  // const rightLen = ~idx ? inorder.length : inorder.length - idx - 1;
  // console.log(idx, leftLen, 'xx')
  // return
  root.left = buildTree(
    preorder.slice(1, 1 + leftLen),
    inorder.slice(0, idx)
  );
  root.right = buildTree(
    preorder.slice(1 + leftLen),
    inorder.slice(idx + 1)
  );
  return root;
};