【Day 17】 从前序与中序遍历序列构造二叉树

题目描述

根据一棵树的前序遍历与中序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如，给出

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

    3

/ \
 9 20
/ \
 15 7
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的回答

解法一

前序遍历的结构是：【根节点】 -> 左子树 -> 右子树

中序遍历的结构是：左子树 -> 【根节点】 -> 右子树

时间复杂度 O(n) n 为节点数

空间复杂度 O(n) 一个 Tree？

var buildTree = function (preorder, inorder) {
    if (!preorder.length ) return null;

    let curVal = preorder[0];
    let root = new TreeNode(curVal);
    let Index = inorder.indexOf(preorder[0]);

    root.left = buildTree(preorder.slice(1, Index + 1),inorder.slice(0, Index))
    root.right = buildTree(preorder.slice(Index + 1),inorder.slice(Index + 1))
    return root
};

参考回答

前序遍历的第一个数 preorder[0]一定是二叉树的根节点，在中序遍历中找到这个节点就可以把中序遍历拆分成左子树的中序遍历leftInorder和右子树的中序遍历rightInorder, 又因为一棵数的前序遍历长度和中序遍历长度是一样，所以可以根据左右中序把前序遍历拆分成leftPreorder和rightPreorder, 这样我们就拿到了左右 子树的preorder和inorder， 接下来递归就可以了

/**
 * 递归写法
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function (preorder, inorder) {
  if (preorder.length === 0) {
    return null;
  }

  let curVal = preorder[0];
  let root = new TreeNode(curVal);
  let inorderIndex = inorder.indexOf(preorder[0]);
  root.left = buildTree(
    preorder.slice(1, inorderIndex + 1),
    inorder.slice(0, inorderIndex)
  );
  root.right = buildTree(
    preorder.slice(inorderIndex + 1),
    inorder.slice(inorderIndex + 1)
  );
  return root;
};