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

#输出二叉树的右视图# 分成两步走:1、递归重建二叉树（参考NC12重建二叉树）时间复杂度O(n),空间O(n)2、层序遍历（使用一个last指针记录每一层的最后一个节点，遍历到每层最后一个节点时，将其加入数组即可)时间复杂度O(n),空间O(n)，总时间复杂度O(n),总空间复杂度O(n)

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型一维数组 先序遍历
     * @param zhongxu int整型一维数组 中序遍历
     * @return int整型一维数组
     */
    public int[] solve (int[] xianxu, int[] zhongxu) {
        // write code here
      TreeNode root  = reConstructTree(xianxu,zhongxu);
       List<TreeNode> list = new ArrayList<>();
        List<Integer> res = new ArrayList<Integer>();
        int front=0;
        int rear = 0;
        int last = 1;
        list.add(rear++,root);
        while(front!=rear){
            TreeNode p = list.get(front++);
            if(p.left!=null)list.add(rear++,p.left);
            if(p.right!=null)list.add(rear++,p.right);
            if(front==last){
                res.add(p.val);
                last = rear;
            }
        }
        int[] a=new int [res.size()];
        int i =0;
        for(int item:res){
            a[i++] =item; 
        }
        return a;
    }
    TreeNode reConstructTree(int[] xianxu, int[] zhongxu) {
        if(xianxu.length==0)return null;
        TreeNode root = new TreeNode(xianxu[0]);
        for(int i=0;i<zhongxu.length;++i){
            if(xianxu[0]==zhongxu[i]){
                root.left = reConstructTree(Arrays.copyOfRange(xianxu,1,i+1),Arrays.copyOfRange(zhongxu,0,i));
                root.right = reConstructTree(Arrays.copyOfRange(xianxu,i+1,xianxu.length),Arrays.copyOfRange(zhongxu,i+1,zhongxu.length));
            }
        }
        return root;
    }
}