剑指 Offer 07. 重建二叉树

剑指 Offer 07. 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：

3
 / \
9  20
  /  \
 15   7

限制：
0 <= 节点个数 <= 5000

注意：本题与主站 105 题重复：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

思路

知识点：前序遍历的第一个节点一定根节点，中序遍历的根节点左边的树一定在左子树，右边的数一定在右子树上。
根据以上知识可以得到一个思路。移除前序遍历数组的第一个元素为根节点，找到根节点在中序遍历数组的下标，分为两个左右两个数组，将前序遍历数组以及左右子树数组递归调用，可以得到结果

解答

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function (preorder, inorder) {
  if (!preorder.length || !inorder.length) return null;
  const node = new TreeNode(preorder.shift());
  const index = inorder.indexOf(node.val);
  node.left = buildTree(preorder, inorder.slice(0, index));
  node.right = buildTree(preorder, inorder.slice(index + 1));
  return node;
};