描述

请根据二叉树的前序遍历，中序遍历恢复二叉树，并打印出二叉树的右视图

如输入[1, 2, 4, 5, 3], [4, 2, 5, 1, 3]时，通过前序遍历的结果[1, 2, 4, 5, 3]和中序遍历的结果[4, 2, 5, 1, 3]可重建出以下二叉树：

所以对应的输出为[1, 3, 5]。

    1
   / \
  2   3
 / \
4   5

链接

BM41 输出二叉树的右视图 Nowcoder

示例

输入：[1,2,4,5,3],[4,2,5,1,3]
返回值：[1,3,5]

题解

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 求二叉树的右视图
 * @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 queue = [root];
        const res = [];
        while (queue.length) {
            const count = queue.length;

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

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

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

        return res;
    }

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

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