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

题目描述

难度：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
  }
};