重建二叉树

题目描述

思路分析

在中序遍历列表中找到先序遍历列表中第一个节点，以此为界限可以将二叉树分为左右子树，可以得知左子树和右子树的长度，在先序遍历列表中划分出来。再依次拿出先序遍历列表中的第一个节点构成左/右子树的根节点，直到传入的先序序列或中序序列为空结束遍历，返回根节点。

代码参考

/*
  前序遍历{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}
*/

const reConstructBinaryTree = function (pre, vin) {
  // 如果为空树则直接返回
  if (!pre.length || !vin.length) return null
  // 前序遍历的第一个元素为根节点
  const root = new TreeNode(pre.shift())
  // 找到root.val在中序遍历中的索引，则数组被分为两部分，左侧为左子树，右侧为右子树
  const index = vin.indexOf(root.val)
  root.left = reConstructBinaryTree(pre, vin.slice(0, index))
  root.right = reConstructBinaryTree(pre.vin.slice(index + 1))
  return root
}