从前序与中序遍历序列构造二叉树
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
示例 1:
codeType
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]
示例 2:
codeType
输入: preorder = [-1], inorder = [-1]
输出: [-1]
提示:
- 1 <= preorder.length <= 3000
- inorder.length == preorder.length
- -3000 <= preorder[i], inorder[i] <= 3000
- preorder 和 inorder 均 无重复 元素
- inorder 均出现在 preorder
- preorder 保证 为二叉树的前序遍历序列
- inorder 保证 为二叉树的中序遍历序列
解法
分治+递归
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(preorder: number[], inorder: number[], preLeft: number, preRight:number, inLeft: number, inRight: number){
if(preLeft > preRight) return null // 递归边界
// preorder的第一个节点就是当前根节点
const root = new TreeNode()
root.val = preorder[preLeft]
// 在inorder中找到这个根节点
const inRoot = map.get(root.val)
// 左子树节点数目 = 根节点索引 - 左边界
const leftTreeSize = inRoot - inLeft
// 构造左子树
root.left = myBuildTree(preorder, inorder, preLeft + 1, preLeft + leftTreeSize, inLeft, inRoot - 1)
// 构造右子树
root.right = myBuildTree(preorder, inorder, preLeft + leftTreeSize + 1, preRight, inRoot + 1, inRight)
return root
}
function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
// 通过两个遍历序列就可以确定一颗二叉树
// 先通过先序序列确认头节点，然后通过中序序列确认左右子树
// 中序节点需要根据值直接查找O(n)，所以可以用哈希表存储值和对应的索引实现O(1)查找
let n = preorder.length
// 构造哈希表定位中序遍历节点
for(let i = 0; i < n; i++){
map.set(inorder[i], i)
}
return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1)
};