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

import java.util.*;


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

    }
    public void  build(int[] xianxu, int[] zhongxu, int level,
                       Map<Integer, List<Integer>> result) {
        if (xianxu.length == 0 || zhongxu.length == 0) {
            return;
        }
        for (int i = 0; i < zhongxu.length; i++) {
            if (xianxu[0] == zhongxu[i]) {
                int[] zx_left = Arrays.copyOfRange(zhongxu, 0, i);
                int[] zx_right = Arrays.copyOfRange(zhongxu, i + 1, zhongxu.length);
                int[] xx_left = Arrays.copyOfRange(xianxu, 1, i + 1);
                int[] xx_right = Arrays.copyOfRange(xianxu, i + 1, xianxu.length);
                build(xx_left, zx_left, level + 1, result); // 先左边
                if (!result.containsKey(level)) {
                    result.put(level, new ArrayList<>());
                }
                List<Integer> list = result.get(level);
                list.add(xianxu[0]);
                build(xx_right, zx_right, level + 1, result); // 再右边
                break;
            }
        }
    }
}

题目和重建二叉树很像，但是在重建的过程中，其实很像中序遍历，我们遍历的过程中，将结果存储在map中，map中保存的结果如下

key:integer

value:list

0层：1

1层：2,3

2层: 5,7,9

最后遍历map获取最后的值即可