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

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 求二叉树的右视图
 * @param xianxu int整型一维数组 先序遍历
 * @param zhongxu int整型一维数组 中序遍历
 * @return int整型一维数组
 */
export function solve(xianxu: number[], zhongxu: number[]): number[] {
    // write code here
    const buildTree = (a = [], b = []) => {
        if(!a.length || !b.length) return  null;
        // 从 中序遍历list找到根节点
        const nodeIndex  = b.findIndex(item => item === a[0]);
        const curNode = new TreeNode(a[0]);
        curNode.left = buildTree(a.slice(1, nodeIndex + 1), b.slice(0, nodeIndex))
        curNode.right = buildTree(a.slice(nodeIndex + 1), b.slice(nodeIndex + 1));
        return curNode;
    }
    const root = buildTree(xianxu, zhongxu);
    if(!root) return [];
    let queue = [root];
    const res = [];
    while(queue.length){
        const next = [];
        // 因为是右 视图，层级遍历 list 最尾部一项 便是从右往左看的第一项;
        res.push(queue[queue.length - 1].val);
        for(const node of queue){
            node.left && next.push(node.left);
            node.right && next.push(node.right);
        }
        queue = next;
    }
    return res;
}