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

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> list = new ArrayList<>();
        TreeNode node = buildTree(preOrder,inOrder);

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(node);
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i = 0;i < size;i++){
                TreeNode tmp = queue.poll();
                if(tmp.left != null){
                    queue.add(tmp.left);
                }

                if(tmp.right != null){
                    queue.add(tmp.right);
                }
                if(i == size - 1){
                    list.add(tmp.val);
                }
            }
        }
        int[] res = new int[list.size()];
        for(int i = 0;i < list.size();i++){
            res[i] = list.get(i);
        }
        return res;
    }

    private TreeNode buildTree(int[] preOrder, int[] inOrder){
         if(preOrder.length == 0 || inOrder.length == 0){
            return null;
        }

        TreeNode node = new TreeNode(preOrder[0]);
        for(int i = 0;i < inOrder.length;i++){
            if(preOrder[0] == inOrder[i]){
                node.left = buildTree(Arrays.copyOfRange(preOrder,1,i+1),Arrays.copyOfRange(inOrder,0,i));
                node.right = buildTree(Arrays.copyOfRange(preOrder,i+1,preOrder.length),Arrays.copyOfRange(inOrder,i+1,inOrder.length));
                break;
            }
        }
        return node;
    }
}