从中序与后续遍历序列构造二叉树
给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
示例 1:
codeType
输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]
示例 2:
codeType
输入：inorder = [-1], postorder = [-1]
输出：[-1]
提示:
- 1 <= inorder.length <= 3000
- postorder.length == inorder.length
- -3000 <= inorder[i], postorder[i] <= 3000
- inorder 和 postorder 都由 不同 的值组成
- postorder 中每一个值都在 inorder 中
- inorder 保证是树的中序遍历
- postorder 保证是树的后序遍历
解法
ts
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
// 用于查找inorder
const map = new Map<number, number>()
function myBuildTree(postorder: number[], inorder: number[], postLeft: number, postRight:number, inLeft: number, inRight: number){
if(postLeft > postRight) return null // 递归边界
// postorder的最后一个节点是根节点
const root = new TreeNode()
root.val = postorder[postRight]
// 在inorder中找到这个根节点
const inRoot = map.get(root.val)
// 左子树节点数目 = 根节点索引 - 左边界
const leftTreeSize = inRoot - inLeft
// 构造左子树
root.left = myBuildTree(postorder, inorder, postLeft, postLeft + leftTreeSize - 1, inLeft, inRoot - 1)
// 构造右子树
root.right = myBuildTree(postorder, inorder, postLeft + leftTreeSize, postRight - 1, inRoot + 1, inRight)
return root
}
function buildTree(inorder: number[], postorder: number[]): TreeNode | null {
// 这个和前序与中序遍历序列构造二叉树的代码基本没区别
// 只不过后续序列的根变成了后
let n = inorder.length
// 构造哈希表定位中序遍历节点
for(let i = 0; i < n; i++){
map.set(inorder[i], i)
}
return myBuildTree(postorder, inorder, 0, n - 1, 0, n - 1)
};