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

• LeetCode - 105. 从前序与中序遍历序列构造二叉树

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

思路

1. 先序遍历的第一个元素对应的是树的根节点
2. 根据 preorder[0]（即根节点）找到其在 inorder 中的位置，根节点左侧为左子树的中序遍历结果，右侧为右子树的中序遍历
3. 根据左子树的长度，在 preorder 中可以得到左右子树的先序遍历结果
4. 递归得到答案

var buildTree = function (preorder, inorder) {
  if (preorder.length === 0) {
    return null
  }
  const rootVal = preorder[0]
  const leftLength = inorder.indexOf(rootVal)
  return new TreeNode(
    rootVal,
    buildTree(preorder.slice(1, leftLength + 1), inorder.slice(0, leftLength)),
    buildTree(preorder.slice(leftLength + 1), inorder.slice(leftLength + 1))
  )
}