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

import java.util.*;


public class Solution {
   
    public int[] solve (int[] preOrder, int[] inOrder) {
        // write code here
        
        ArrayList<Integer> ret = new ArrayList<>();
        TreeNode root =build(preOrder,inOrder);
        TreeNode cur = root;
        //层序遍历。得到每一层最右边
        //队列进行先进先出
        Queue<TreeNode> q = new LinkedList<>();

       
        //先将根节点加入
        q.add(root);
        while(!q.isEmpty()){
            //记录当前队列大小，记录一层的节点数
            int n = q.size();
           //ArrayList<Integer> tmp = new ArrayList<>();
            for(int i=0;i<n;i++){
                TreeNode t = q.poll();
                //tmp.add(t.val);
                //为一层最后一个时
                if(i==n-1) ret.add(t.val);
                //同时将这一个节点的子节点加入队列
                //以下新增加的节点与n无关属于下一层
                if(t.left!=null){
                    q.add(t.left);
                }
                if(t.right!=null){
                    q.add(t.right);
                }
            }
        }
         int[] ret2 = new int[ret.size()];
         for(int i=0;i<ret.size();i++){
            ret2[i] = ret.get(i);
         }

        return ret2;
    }
    //建树
    private static TreeNode build(int[] preOrdder,int[] inOrder){
        int n =preOrdder.length;
        int m = inOrder.length;

        if(n==0||m==0) return null;

        TreeNode root = new TreeNode(preOrdder[0]);

        //建树
        for(int i=0;i<inOrder.length;i++){
            if(preOrdder[0]==inOrder[i]){
                //找到根节点
                root.left = build(Arrays.copyOfRange(preOrdder,1,i+1),Arrays.copyOfRange(inOrder,0,i));
                root.right = build(Arrays.copyOfRange(preOrdder,i+1,preOrdder.length),Arrays.copyOfRange(inOrder,i+1,inOrder.length));
            }
        }
        return root;



        
    }
}