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

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 求二叉树的右视图
 * @param preOrder int整型一维数组 先序遍历
 * @param inOrder int整型一维数组 中序遍历
 * @return int整型一维数组
 */
function solve(preOrder, inOrder) {
    // write code here

    function rebuild(_pre, _in) {
        if (!_pre.length && !_in.length) return null;
        const root = new TreeNode(_pre[0]);
        const index = _in.indexOf(_pre[0]);
        root.left = rebuild(_pre.slice(1, index + 1), _in.slice(0, index));
        root.right = rebuild(_pre.slice(index + 1), _in.slice(index + 1));
        return root;
    }

    function rightSideView(root) {
        const quque = [root];
        const res = [];
        while (quque.length) {
           
            const count = quque.length;

            // 每一次循环是一层，把一层的全部拿出去 再找到子节点全部加进来
            // 每一层最右边的节点 就是这一层的右视图
            for (i = 0; i < count; i++) {
                const node = quque.shift();

                if (i === count - 1) {
                    res.push(node.val);
                }

                node.left && quque.push(node.left);
                node.right && quque.push(node.right);
            }
        }

        return res;
    }

    // 重建二叉树
    const tree = rebuild(preOrder, inOrder);
    // 层序遍历 输出每一层的最右侧的节点
    const res = rightSideView(tree);

    return res;
}
module.exports = {
    solve: solve,
};