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

import java.util.*;


public class Solution {

    private Map<Integer, Integer> map = new HashMap<>();

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型一维数组 先序遍历
     * @param zhongxu int整型一维数组 中序遍历
     * @return int整型一维数组
     */
    public int[] solve (int[] pre, int[] in) {
        // write code here
        if (pre == null || in == null) {
            return new int[0];
        }
        for (int i = 0; i < in.length; i++) {
            map.put(in[i], i);
        }
        TreeNode root = reconstruct(pre, 0, pre.length - 1, in, 0, in.length - 1);
        List<List<Integer>> list = levelOrder(root);
        int[] res = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            List<Integer> level = list.get(i);
            res[i] = level.get(level.size() - 1);
        }
        return res;
    }

    private List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode cur = root;
        queue.offer(cur);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> level = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                cur = queue.poll();
                level.add(cur.val);
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            res.add(level);
        }
        return res;
    }

    private TreeNode reconstruct(int[] pre, int pi, int pj, int[] in, int ni, int nj) {
        if (pi > pj) {
            return null;
        }
        TreeNode root = new TreeNode(pre[pi]);
        int index = map.get(pre[pi]);
        root.left = reconstruct(pre, pi + 1, pi + index - ni, in, ni, index - 1);
        root.right = reconstruct(pre, pi + index - ni + 1, pj, in, index + 1, nj);
        return root;
    }

    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }
}