Cocolib

Appearance

On this page

从中序与后序遍历序列构造二叉树 ​

Question

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

image-20230613121812332

已知后序与中序求前序序列 ​

后序：9,15, 7, 20, 3（左右根） 中序：9, 3, 15, 20, 7（左根右）

分析：后序序列的最后一位就是树的根节点，在中序序列中找到该根节点，则根节点的左右部分即为左右子树

后序：(9) (15 7 20) 3
中序：(9) 3 (15 20 7)

如果让我们肉眼看两个序列，画一棵二叉树的话，应该分分钟都可以画出来。

流程如图：

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

那么代码应该怎么写呢？

说到一层一层切割，就应该想到了递归。

来看一下一共分几步：

  • 第一步：如果数组大小为零的话，说明是空节点了。
  • 第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。
  • 第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点
  • 第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）
  • 第五步：切割后序数组，切成后序左数组和后序右数组
  • 第六步：递归处理左区间和右区间

递归的返回值是TreeNode

js
var buildTree = function(inorder, postorder) {
    if(inorder.length===0||postorder.length===0)   return null	
    
    const root = new TreeNode()
    let node = postorder.pop()	
    let index = inorder.findIndex( (element) => element === node)	
    root.val = node
    console.log(root)
    let leftin = inorder.slice(0,index)
    let rightin = inorder.slice(index+1,inorder.length)
    let leftpost = postorder.slice(0,index)
    let rightpost = postorder.slice(index,postorder.length)
    root.left = buildTree(leftin,leftpost)
    root.right = buildTree(rightin,rightpost)
    return root
};