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

[FE-Sadhu]

题目

思路：

前序遍历的值的结果 === [根节点，[左子树的前序遍历结果]， [右子树的前序遍历结果]]

中序遍历的值的结果 === [[左子树的中序遍历结果]，根节点，[右子树的中序遍历结果]]

我们方法的定义是，输入一个二叉树的前序遍历结果、中序遍历结果，返回构建好的二叉树的根节点。

所以我们可以先根据 左子树的前序/中序遍历结果 求出左子树，同样再求出右子树，最终拼接上根节点就是我们想要的结果了。

代码实现：

var buildTree = function(preorder, inorder) {
  if (!preorder.length) {
    return null;
  }
  const index = inorder.findIndex(v => v === preorder[0]); // 可以用 hash 表优化，不用每次都遍历查找
  const leftInorder = inorder.slice(0, index);
  const rightInorder = inorder.slice(index + 1);
  const restPreorder = preorder.slice(1);
  const leftPreorder = restPreorder.slice(0, leftInorder.length);
  const rightPreorder = restPreorder.slice(index2);
  const root = new TreeNode(preorder[0]);
  root.left = buildTree(leftPreorder, leftInorder);
  root.right = buildTree(rightPreorder, rightInorder);
  return root;
};

时间复杂度: O(m * n) m 为递归的次数、n 为每次在中序数组中遍历找根节点位置的操作
空间复杂度: O(n) n 为函数调用栈的栈深