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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求二叉树的右视图
     * @param preOrder int整型一维数组 先序遍历
     * @param inOrder int整型一维数组 中序遍历
     * @return int整型一维数组
     */
    Map<Integer, Integer> map;
    public int[] solve (int[] preOrder, int[] inOrder) {
        // write code here
        TreeNode root = buildTree(preOrder, inOrder);
        // 层序遍历
        Queue<TreeNode> que = new LinkedList<>();
        int tmp = 0;
        List<Integer> list = new ArrayList<>();
        que.offer(root);

        while(!que.isEmpty()) {
            int size = que.size();
            
            while(size-- > 0) {
                TreeNode node = que.poll();
                if(node.left != null) {
                    que.offer(node.left);
                }
                if(node.right != null) {
                    que.offer(node.right);
                }
                tmp = node.val;
            }

            list.add(tmp);
            
        }

        int[] arr = new int[list.size()];
        for(int i = 0; i < list.size(); i++) {
            arr[i] = list.get(i);
        }
        return arr;


        
    }

    public TreeNode buildTree(int[] preOrder, int[] inOrder) {
        map = new HashMap<>();
        for(int i = 0; i < inOrder.length; i++) {
            map.put(inOrder[i], i);
        }
        return findNode(preOrder, 0, preOrder.length, inOrder, 0, inOrder.length);
    }

    public TreeNode findNode(int[] preOrder, int preBegin, int preEnd, int[] inOrder, int inBegin, int inEnd) {
        if(preBegin >= preEnd || inBegin >= inEnd) return null;

        int val = preOrder[preBegin];
        int rootIdx = map.get(val);
        TreeNode root = new TreeNode(val);
        int lenOfLeft = rootIdx - inBegin;


        root.left = findNode(preOrder, preBegin+1, preBegin+1+lenOfLeft, inOrder, inBegin, rootIdx);
        root.right = findNode(preOrder, preBegin + lenOfLeft + 1, preEnd, inOrder,rootIdx + 1, inEnd);

        return root;

    }
}