[NC]136. 输出二叉树的右视图【重建二叉树 右视图】

🚩传送门：牛客题目

题目

请根据二叉树的 前序 遍历， 中序 遍历恢复二叉树，并打印出二叉树的右视图

示例1：

输入：[1,2,4,5,3],[4,2,5,1,3] 返回值：[1,3,5] 解释： 如输入[1,2,4,5,3],[4,2,5,1,3]时，通过前序遍历的结果[1,2,4,5,3]和后序遍历的结果[4,2,5,1,3]可重建出以下二叉树：

解题思路：重建+右视图

🚩重建代码讲解：https://www.yuque.com/qingxuan-u4juc/leetcode/wqyh2i

🚩视图代码讲解：https://www.yuque.com/qingxuan-u4juc/leetcode/cq70s0

我的代码

public class Solution {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
     //重建二叉树
     TreeNode ReConstuct(int[] preOrder, int[] midOrder){
        if(preOrder==null||preOrder.length==0||midOrder==null||midOrder.length==0) return null;
        TreeNode root= new TreeNode(preOrder[0]);
        for(int i=0;i<midOrder.length;i++){
            if(midOrder[i]==preOrder[0]){
                root.left=ReConstuct(Arrays.copyOfRange(preOrder,1,i+1),Arrays.copyOfRange(midOrder,0,i));
                root.right=ReConstuct(Arrays.copyOfRange(preOrder,i+1,preOrder.length),Arrays.copyOfRange(midOrder,i+1,midOrder.length));
                break;
            }
        }
        return root;
    }
     //右视图
     int[] RightViewTree(TreeNode node){
        Queue<TreeNode> queue=new LinkedList<>();
        List<Integer> res=new LinkedList<>();
        if(node==null)return new int[]{};
        queue.add(node);
        while(!queue.isEmpty()){
            int size=queue.size();
            //3. 队列的循环开始的第一个一定是最右边的结点
            res.add(queue.peek().val);
            //4. 通过size控制每一层循环的个数
            for(int i=0;i<size;i++){
                //5. 先右后左,每一层的第一个结点一定是最右边结点
                if(queue.peek().right!=null)
                    queue.add(queue.peek().right);
                if(queue.peek().left!=null)
                    queue.add(queue.peek().left);
                queue.poll();
            }
        }
        return res.stream().mapToInt(Integer::intValue).toArray();
    }
    public  int[] solve(int[] xianxu, int[] zhongxu) {
        //1.重建二叉树
        TreeNode root=ReConstuct(xianxu,zhongxu);
        //2.返回视图数组
        return RightViewTree(root);
    }
}