原文：105. 从前序与中序遍历序列构造二叉树(leetcode 解题) - 每天一个JavaScript小知识@Js中文网 · 码农进阶题库

原文地址：https://www.javascriptc.com/interview-tips/zh_cn/leetcode/leetcode-javascript-solution-0105/

题目：

难度：Middle

相关话题：树、深度优先搜索、数组

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

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

例如，给出

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

返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7

思路：

按照preorder的顺序从inorder内部查找，对于查找到的索引idx，将当前inorder的左lo和右hi边界继续分割为[lo,idx-1]和[idx+1,hi]，继续递归处理。

和NO.106的区别在于preorder需要从左向右，并且先left子树再right子树。

/**
 * @来源： Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍：一个致力于帮助开发者用代码改变世界为使命的平台，每天都可以在这里找到技术世界的头条内容
 * 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) {
  let preIdx=0
  return createTree(0,inorder.length-1)

  function createTree(lo,hi){
    if(lo>hi)return null
    let val=preorder[preIdx++]
    let idx=inorder.indexOf(val)
    let node=new TreeNode(val)
    node.left=createTree(lo,idx-1)
    node.right=createTree(idx+1,hi)
    return node
  }
};