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

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

题目:

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

扩展阅读: