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

import java.util.*;


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

        List<Integer> preList = new ArrayList<>();
        List<Integer> inList = new ArrayList<>();
        int loopPre = preOrder.length;
        for (int i = 0; i < loopPre; i++) {
            preList.add(preOrder[i]);
        }
        int loopIn = inOrder.length;
        for (int i = 0; i < loopIn; i++) {
            inList.add(inOrder[i]);
        }

        targetMap.put(0, preList.get(0));
        NodeList target = buildTree(preList, inList, null, 1);//重组二叉树

        int[] targetArr = new int[targetMap.size()];
        int i = 0;
        for (Map.Entry<Integer, Integer> entry : targetMap.entrySet()) {
            targetArr[i] = entry.getValue();
            i++;
        }
        return targetArr;
    }

    private Map<Integer, Integer> targetMap = new TreeMap<>(); //按照层级默认升序排序

    public NodeList buildTree(List<Integer> preList, List<Integer> inList,
                              NodeList target, int level) {
        if (preList == null || preList.size() == 0) return null;
        int rootVal = preList.get(0);
        target = new NodeList(rootVal);

        int rootIndex = inList.indexOf(rootVal);

        List<Integer> inListLeft = null;
        List<Integer> inListRight = null;
        List<Integer> preListLeft = null;
        List<Integer> preListRight = null;
        if (rootIndex > 0) {
            inListLeft = inList.subList(0, rootIndex);
            preListLeft = preList.subList(1, inListLeft.size()+1);
        }
        if (rootIndex < inList.size() - 1) {
            inListRight = inList.subList(rootIndex + 1, inList.size());
            preListRight = preList.subList(preList.size() - inListRight.size(),  preList.size());
        }

        NodeList left = buildTree(preListLeft, inListLeft, target.left, level + 1);
        if (left != null) {
            target.left = left;
            targetMap.put(level, left.val);//当前层级无右节点时，该左节点就是最右侧节点
        }
        NodeList right = buildTree(preListRight, inListRight, target.right, level + 1);
        if (right != null) {
            target.right = right;
            targetMap.put(level, right.val);//有右节点时打印右节点，使用map的特性，key相同，覆盖值
        }

        return target;
    }

    class NodeList {
        int val;
        NodeList left;
        NodeList right;
        public NodeList(int val) {
            this.val = val;
        }
    }
}