题目:
难度:Middle
相关话题:树
、深度优先搜索
、数组
根据一棵树的中序遍历与后序遍历构造二叉树。
注意: 你可以假设树中没有重复的元素。
例如,给出
中序遍历 inorder =[9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树:
思路:
按照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)
};
扩展阅读: