【每日一题】105 从前序与中序遍历序列构造二叉树

题目地址：105. 从前序与中序遍历序列构造二叉树 (opens new window)

题意：

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

注意:

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

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7

思路

思路来自题解LeetCode@alexer-660 (opens new window)。

前序遍历是指二叉树的根节点（子树则是子树的根节点）首先遍历，而中序遍历则是指先遍历二叉树的左边叶子节点，再遍历根节点，接着才是左边叶子节点。

---

👉 分析题意：

由定义可知，前序遍历序列的第一个值即为二叉树的根节点的值。求其在在中序遍历序列中的索引，就可以得到其左子树和右子树的中序遍历序列。

• 前序遍历：[3, 9, 20, 15, 7] -> 根节点的值为3
• 中序遍历：[9, 3, 15, 20, 7] -> 在中序遍历序列中的索引为index = 1

根节点的值3在中序遍历中的索引index为1，其将序列分成两部分，[9]即为二叉树的左子树的中序遍历序列，而[15, 20, 7]则是二叉树的右子树的中序遍历序列。

👉 那么左右子树的前序遍历序列呢？

根节点的值在中序遍历序列中的索引为index = 1，可以得到二叉树的左子树的节点个数为1，而二叉树的右子树的节点个数自然是3了。

由于前序遍历先根节点，在左子树，接着右子树，那么根据左右子树的节点个数，自然可以从前序遍历序列中获取到左右子树的前序遍历序列。👇

前序遍历：[3] 根 / [9] 左 / [20, 15, 7] 右 。

递归解法（来自题解）

/**
 * 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) return null;
  const root = new TreeNode(preorder[0]);// 根节点应为前序遍历第一个节点
  const 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;
};