LeetCode 106. 从中序与后序遍历序列构造二叉树

题目描述

难度：Middle

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

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

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

例如，给出

中序遍历 inorder =[9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]

返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7

---

思路：

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

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

/**
 * @ Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} inorder
 * @param {number[]} postorder
 * @return {TreeNode}
 */
var buildTree = function(inorder, postorder) {
  let postIdx=postorder.length-1
  function createTree(lo,hi){
    if(lo>hi)return null
    let val=postorder[postIdx--]
    let idx=inorder.indexOf(val)
    let node=new TreeNode(val)
    node.right=createTree(idx+1,hi)
    node.left=createTree(lo,idx-1)
    return node
  }
  return createTree(0,inorder.length-1)
};