题解 | #输出二叉树的右视图#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 求二叉树的右视图
 * @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
}