LeetCode.106 - 从中序与后序遍历序列构造二叉树

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

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

思路

1. 后序遍历的最后一个元素对应的是树的根节点
2. 根据 postorder[-1]（即根节点）找到其在 inorder 中的位置，根节点左侧为左子树的中序遍历结果，右侧为右子树的中序遍历
3. 根据左子树的长度，在 postorder 中可以得到左右子树的先序遍历结果
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))
  )
}