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

import java.util.*;


public class Solution {
    private Map<Integer, Integer> map = new HashMap<>();
    private List<Integer> res = new ArrayList<>();
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求二叉树的右视图
     * @param preOrder int整型一维数组 先序遍历
     * @param inOrder int整型一维数组 中序遍历
     * @return int整型一维数组
     */
    public int[] solve (int[] preOrder, int[] inOrder) {
        if (preOrder.length == 0) {
            return null;
        }

        for (int i = 0; i < inOrder.length; ++i) {
            map.put(inOrder[i], i);
        }
        // 建树
        TreeNode root = reBuild(preOrder, 0, preOrder.length - 1, inOrder, 0, inOrder.length - 1);
        // 层级遍历
        return rightSideView(root);
    }

    private TreeNode reBuild(int[] preOrder, int pl, int pr, int[] inOrder, int il, int ir) {
        if (pl > pr) {
            return null;
        }

        TreeNode node = new TreeNode(preOrder[pl]);
        int index = map.get(preOrder[pl]);
        node.right = reBuild(preOrder, pl + index - il + 1, pr, inOrder, index + 1, ir);
        node.left = reBuild(preOrder, pl + 1, pl + index - il, inOrder, il, index - 1);
        return node;
    }

    private int[] rightSideView(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        List<Integer> res = new ArrayList<>();
        while (!queue.isEmpty()) {
            int size = queue.size();
            TreeNode node = null;
            while (--size >= 0) {
                node = queue.poll();    
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            res.add(node.val);
        }

        return res.stream().mapToInt(Integer::intValue).toArray();
    }
}