/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
* 求二叉树的右视图
* @param xianxu int整型一维数组 先序遍历
* @param zhongxu int整型一维数组 中序遍历
* @return int整型一维数组
*/
/**
* 方法一:递归
* 时间复杂度:
* 空间复杂度:
*/
export function solve(xianxu: number[], zhongxu: number[]): number[] {
let level: number = 0
const res: number[] = []
rebuild(xianxu, zhongxu, level, res)
return res
}
function rebuild(xianxu: number[], zhongxu: number[], level: number, res: number[]) {
if (xianxu.length === 0) return null
const root = xianxu[0]
const index = zhongxu.findIndex((node) => {
return node === root
})
//左子树的先序遍历结果
const leftNodePreOrder = xianxu.slice(1, index + 1)
//左子树的中序遍历结果
const leftNodeInOrder = zhongxu.slice(0, index)
//右子树的先序遍历结果
const rightNodePreOrder = xianxu.slice(index + 1)
//右子树的中序遍历结果
const rightNodeInOrder = zhongxu.slice(index + 1)
rebuild(leftNodePreOrder, leftNodeInOrder, level + 1, res)
rebuild(rightNodePreOrder, rightNodeInOrder, level + 1, res)
//记录下每一层的
res[level] = root
}