输出二叉树的右视图

import java.util.*;

/**
 * NC136 输出二叉树的右视图
 * @author d3y1
 */
public class Solution {
    private ArrayList<Integer> list = new ArrayList<>();

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求二叉树的右视图
     * 
     * 相似 -> NC12 重建二叉树 [nowcoder]
     * 相似 -> NC223 从中序与后序遍历序列构造二叉树 [nowcoder]
     * 
     * @param preOrder int整型一维数组 先序遍历
     * @param inOrder int整型一维数组 中序遍历
     * @return int整型一维数组
     */
    public int[] solve (int[] preOrder, int[] inOrder) {
        return solution1(preOrder, inOrder);
        // return solution2(preOrder, inOrder);
    }

    // val -> idx
    private HashMap<Integer,Integer> inMap = new HashMap<>();
    private int preRootIdx = 0;

    /**
     * 前序遍历 + 层序遍历
     * @param preOrder
     * @param inOrder
     * @return
     */
    private int[] solution1(int[] preOrder, int[] inOrder){
        int n = inOrder.length;
        if(n == 0){
            return new int[]{};
        }

        for(int i=0; i<n; i++){
            inMap.put(inOrder[i], i);
        }

        // 构建树
        TreeNode root = build(preOrder, 0, n-1);
        // 右视图
        levelOrder(root);

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

        return result;
    }

    /**
     * 递归遍历(前序)
     *
     * 二叉树前序遍历: 根 -> 左 -> 右
     * 可利用该性质直接找到前序遍历根节点, 子树遍历先左后右: (根) -> 左 -> 右
     *
     * @param preOrder
     * @param inLeft
     * @param inRight
     * @return
     */
    private TreeNode build(int[] preOrder, int inLeft, int inRight){
        if(inLeft > inRight){
            return null;
        }

        // 根
        int preRootVal = preOrder[preRootIdx++];
        TreeNode root = new TreeNode(preRootVal);

        if(inLeft == inRight){
            return root;
        }

        // 中序遍历根结点索引
        int inRootIdx = inMap.get(preRootVal);

        // 左
        root.left = build(preOrder, inLeft, inRootIdx-1);
        // 右
        root.right = build(preOrder, inRootIdx+1, inRight);


        return root;
    }

    /**
     * 前序遍历 + 层序遍历
     * @param preOrder
     * @param inOrder
     * @return
     */
    private int[] solution2(int[] preOrder, int[] inOrder){
        int n = inOrder.length;
        if(n == 0){
            return new int[]{};
        }

        // 构建树
        TreeNode root = construct(preOrder, inOrder);
        // 右视图
        levelOrder(root);

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

        return result;
    }

    /**
     * 递归(前序)
     * @param preOrder
     * @param inOrder
     * @return
     */
    public TreeNode construct(int[] preOrder, int[] inOrder){
        int n = preOrder.length;
        if(n == 0){
            return null;
        }
        // 当前根结点
        int rootVal = preOrder[0];
        TreeNode root = new TreeNode(rootVal);

        // 当前根结点 左子树节点个数
        int left = 0;
        while(inOrder[left] != rootVal){
            left++;
        }
        if(left > 0){
            root.left = construct(Arrays.copyOfRange(preOrder, 1, left+1), Arrays.copyOfRange(inOrder, 0, left));
        }

        // 当前根结点 右子树节点个数
        int right = n-(left+1);
        if(right > 0){
            root.right = construct(Arrays.copyOfRange(preOrder, left+1, n), Arrays.copyOfRange(inOrder, left+1, n));
        }

        return root;
    }

    /**
     * 层序遍历
     * @param root
     */
    private void levelOrder(TreeNode root){
        // 双端队列
        Deque<TreeNode> deque = new ArrayDeque<>();
        deque.offerLast(root);

        int size;
        TreeNode tNode;
        while(!deque.isEmpty()){
            size = deque.size();
            list.add(deque.peekLast().val);
            while(size-- > 0){
                tNode = deque.pollFirst();
                if(tNode.left != null){
                    deque.offerLast(tNode.left);
                }
                if(tNode.right != null){
                    deque.offerLast(tNode.right);
                }
            }
        }
    }
    
    private class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
        public TreeNode(int val){
            this.val = val;
        }
    }
}

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求二叉树的右视图
     * @param preOrder int整型一维数组 先序遍历
     * @param inOrder int整型一维数组 中序遍历
     * @return int整型一维数组
     */
    public int[] solve (int[] preOrder, int[] inOrder) {
        // write code here
        List<Integer> rightViewList = new LinkedList<>();
        TreeNode root = reConstructBinaryTree(preOrder, inOrder);
        rightViewList = findRightReview(root);
        int[] res = new int[rightViewList.size()];
        for (int i = 0; i < rightViewList.size(); i++) {
            res[i] = rightViewList.get(i);
        }
        return res;
    }

    // 重建二叉树 递归
    public TreeNode reConstructBinaryTree (int[] preOrder, int[] vinOrder) {
        // write code here
        if (preOrder.length == 0 || vinOrder.length == 0) return null;
        TreeNode root = new TreeNode(preOrder[0]);
        for (int i = 0; i < vinOrder.length; i++) {
            if (root.val == vinOrder[i]) {
                root.left = reConstructBinaryTree(Arrays.copyOfRange(preOrder, 1, i + 1),
                                                  Arrays.copyOfRange(vinOrder, 0, i));
                root.right = reConstructBinaryTree(Arrays.copyOfRange(preOrder, i + 1,
                                                   preOrder.length),
                                                   Arrays.copyOfRange(vinOrder, i + 1, vinOrder.length));
                break;
            }
        }
        return root;
    }

    // 找出二叉树右视图 层次遍历法
    public List<Integer> findRightReview(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()) {
            int qLength = q.size();
            for (int i = 0; i < qLength; i++) {
                TreeNode temp = q.poll();
                if (temp.left != null) {
                    q.add(temp.left);
                }
                if (temp.right != null) {
                    q.add(temp.right);
                }
                if (i == qLength - 1) {
                    res.add(temp.val);
                }
            }
        }
        return res;
    }
}

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> result = new ArrayList<>();
        if (preOrder.length < 1 || preOrder.length != inOrder.length) {
            return null;
        }
        // 根据前序遍历和中序遍历构造二叉树
        TreeNode root = buildTree(preOrder, 0, preOrder.length - 1, inOrder, 0, inOrder.length - 1);
        if (root == null) {
            return null;
        }
        // 使用迭代法寻找二叉树的最右侧节点
        Deque<TreeNode> queue = new LinkedList<>();
        queue.addLast(root);
        while (!queue.isEmpty()) {
            // 求出每层节点的数量
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.removeFirst();
                // size - 1即为最右侧节点，加入到result结果列表中
                if (i == size - 1) {
                    result.add(node.val);
                }
                if (node.left != null) {
                    queue.addLast(node.left);
                }
                if (node.right != null) {
                    queue.addLast(node.right);
                }
            }
        }
        return result.stream().mapToInt(x -> x).toArray();
    }

    // 根据前序遍历和中序遍历构造二叉树
    public TreeNode buildTree(int[] preOrder, int preStart, int preEnd, int[] inOrder, int inStart, int inEnd) {
        if (preStart > preEnd || inStart > inEnd) {
            return null;
        }
        int root_val = preOrder[preStart];
        TreeNode root = new TreeNode(root_val);
        int index = 0;
        for (index = 0; index < inOrder.length; index++) {
            if (inOrder[index] == root_val) {
                break;
            }
        }
        int left_length = index - inStart;
        root.left = buildTree(preOrder, preStart + 1, preStart + left_length, inOrder, inStart, index - 1);
        root.right = buildTree(preOrder, preStart + left_length + 1, preEnd, inOrder, index + 1, inEnd);
        return root;
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求二叉树的右视图
     * @param preOrder int整型一维数组 先序遍历
     * @param inOrder int整型一维数组 中序遍历
     * @return int整型一维数组
     */
    int index=0;
    ArrayList<Integer> result=new ArrayList<>();
    public int[] solve (int[] preOrder, int[] inOrder) {
        // write code here
        int deep=0;
        ArrayList<Integer>list=new ArrayList<>();
        for(int i=0;i<inOrder.length;i++){
            list.add(inOrder[i]);
        }
        a(list,preOrder,0,result);
        int[] r=new int[result.size()];
        for(int i=0;i<r.length;i++){
            r[i]=result.get(i);
        }
        return r;
    }
    public void a( ArrayList<Integer>list,int[] preOrder,int deep,ArrayList<Integer>result){
        if(list.size()<=0||index==preOrder.length)return;
        if(deep>=result.size())
            result.add(preOrder[index]);
        else
            result.set(deep,preOrder[index]);
        int flag=0;
        ArrayList<Integer>left=new ArrayList<>();
        ArrayList<Integer>right=new ArrayList<>();
        for(int b:list){
            if(b==preOrder[index]){
                flag=1;
                continue;
            }
            if(flag==0)
                left.add(b);
            else
                right.add(b);
        }
        index++;
        a(left,preOrder,deep+1,result);
        a(right,preOrder,deep+1,result);
    }
}

import java.util.*;


public class Solution {
    // 将哈希表创建在成员变量的位置,这样就不用在参数中传递了
    private HashMap<Integer,Integer> map = new HashMap<>();

    // 根据前序遍历和中序遍历构建二叉树
    private TreeNode buildTree(int[] preOrder, int[] inOrder) {
        // 1. 将中序遍历的结果放到哈希表中
        for(int i = 0;i < inOrder.length;i++) {
            map.put(inOrder[i],i);
        }

        // 2. 调用具体的构造二叉树的方法
        return process(preOrder,0,preOrder.length - 1,inOrder,0,inOrder.length - 1);
    }

    // 构造二叉树
    private TreeNode process(int[] preOrder,int l1,int r1,int[] inOrder,int l2,int r2) {
        // 1. 递归退出条件
        if(l1 > r1) {
            return null;
        }

        // 2. 构造根节点
        TreeNode root = new TreeNode(preOrder[l1]);

        // 3. 找出中序遍历根节点的位置
        int find = map.get(preOrder[l1]);

        // 4. 左右递归连接根节点
        root.left = process(preOrder,l1 + 1,l1 + find - l2,inOrder,l2,find - 1);
        root.right = process(preOrder,l1 + find - l2 + 1,r1,inOrder,find + 1,r2);

        // 5. 返回根节点
        return root;
    }

    public int[] solve (int[] preOrder, int[] inOrder) {
        // 1. 参数校验
        if(preOrder == null || inOrder == null || preOrder.length != inOrder.length) {
            return null;
        }

        // 2. 创建出二叉树
        TreeNode root = buildTree(preOrder,inOrder);

        // 3. 创建辅助队列
        Queue<TreeNode> queue = new LinkedList<>();

        // 4. 创建答案数组
        ArrayList<Integer> result = new ArrayList<>();

        // 5. 将根节点加入到队列中
        if(root != null) {
            queue.offer(root);
        }

        // 6. 队列不为空,弹出队列的元素,判断他有没有左右子树,有的话加入到队列中
        while(!queue.isEmpty()) {
            // 7. 获取当前队列的元素个数(当层的元素个数)
            int size = queue.size();

            // 8. 创建 ret 表示该层最后一个元素
            int ret = 0;

            // 9. 遍历 size 个节点
            while(size-- != 0) {
                // 10. 弹出队首元素
                TreeNode cur = queue.poll();

                // 11. 更新 ret 
                ret = cur.val;

                // 12. 判断是否有左右子树
                if(cur.left != null) {
                    queue.offer(cur.left);
                }
                if(cur.right != null) {
                    queue.offer(cur.right);
                }
            }

            // 13. ret 保存了该层最后一个节点的值
            result.add(ret);
        }

        // 14. 将顺序表转化层数组返回
        int[] ans = new int[result.size()];
        for(int i = 0;i < result.size();i++) {
            ans[i] = result.get(i);
        }
        return ans;
    }
}

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求二叉树的右视图
     * @param preOrder int整型一维数组 先序遍历
     * @param inOrder int整型一维数组 中序遍历
     * @return int整型一维数组
     */
    public int[] solve (int[] pre, int[] in) {
        // write code here
        //拿到根节点，层序遍历，每次遍历到每层的最后一个结点加入到ArrayList中
        TreeNode root = solveRoot(pre , in) , temp;
        ArrayList<Integer> arr = new ArrayList<>();
        Queue<TreeNode> q = new ArrayDeque<>();
        q.add(root);
        while(!q.isEmpty()){
            int k = q.size();
            for (int i = 0; i < k; i++) {
                temp = q.poll();
                if(i == k - 1){
                    arr.add(temp.val);
                }
                if(temp.left != null)
                    q.add(temp.left);
                if(temp.right != null)
                    q.add(temp.right);
            }
        }
        int[] res = new int[arr.size()];
        for (int i = 0; i < arr.size(); i++) {
            res[i] = arr.get(i);
        }
        return res;
    }

    //复原树返回根节点
    public TreeNode solveRoot(int[] pre , int[] in){
        int n = pre.length;
        int m = in.length;
        if(n == 0 || m == 0){
            return null;
        }
        TreeNode node = new TreeNode(pre[0]);
        for (int i = 0; i < m; i++) {
            if(pre[0] == in[i]){
                node.left = solveRoot(Arrays.copyOfRange(pre , 1 , i + 1) , Arrays.copyOfRange(in , 0 , i));
                node.right = solveRoot(Arrays.copyOfRange(pre , i + 1 , n) , Arrays.copyOfRange(in , i + 1 , m));
                break;
            }
        }
        return node;
    }
}

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求二叉树的右视图
     * @param preOrder int整型一维数组 先序遍历
     * @param inOrder int整型一维数组 中序遍历
     * @return int整型一维数组
     */
    Map<Integer,Integer> map=new HashMap<>();
    public int[] solve (int[] preOrder, int[] inOrder) {
        for(int i=0;i<inOrder.length;i++){
            map.put(inOrder[i],i);
        }
        TreeNode root=build(preOrder,0,preOrder.length,inOrder,0,inOrder.length);
        //层序遍历
        List<Integer> list=new ArrayList<>();
        Deque<TreeNode> qu=new LinkedList<>();
        qu.offer(root);
        while(!qu.isEmpty()){
            int level=qu.size();
            ArrayList<Integer> levelList=new ArrayList<>();
            for(int i=0;i<level;i++){
                TreeNode peek=qu.peekFirst();
                levelList.add(qu.pollFirst().val);
                if(peek.left!=null) qu.offerLast(peek.left);
                if(peek.right!=null) qu.offerLast(peek.right);
                if(i==level-1){//当遍历到了最后一层，才加入ans
                    list.add(peek.val);
                }
            }
        }
        int[] ans=new int[list.size()];
        for(int i=0;i<list.size();i++){
            ans[i]=list.get(i);
        }
        return ans;
    }
    public TreeNode build(int[] preOrder,int preBegin,int preEnd,int[] inOrder,int inBegin,int inEnd){
        if(preBegin>=preEnd||inBegin>=inEnd){
            return null;
        }
        int rootIndex=map.get(preOrder[preBegin]);
        TreeNode root=new TreeNode(preOrder[preBegin]);
        int leftValue=rootIndex-inBegin;

        root.left=build(preOrder,preBegin+1,preBegin+1+leftValue,inOrder,inBegin,rootIndex);
        root.right=build(preOrder,preBegin+1+leftValue,preEnd,inOrder,rootIndex+1,inEnd);
        return root;

    }

import java.util.*;


public class Solution {

    public int[] solve (int[] xianxu, int[] zhongxu) {
        // write code here
        //先序
        List<Integer> preList=new ArrayList<>();
        //中序
        List<Integer> midList=new ArrayList<>();
        for(int i=0;i<xianxu.length;i++){
            preList.add(xianxu[i]);
            midList.add(zhongxu[i]);
        }
        //构建树
        TreeNode root=getTree(preList,midList);
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        ArrayList<Integer> getResult=new ArrayList<>();
        //层序遍历获取最右边的值
        while(!queue.isEmpty()){
            int size=queue.size();
            for(int i=0;i<size;i++){
                TreeNode node=queue.poll();
                if(i==size-1){
                    getResult.add(node.val);
                }
                if(node.left!=null){
                    queue.add(node.left);
                }
                if(node.right!=null){
                    queue.add(node.right);
                }
            }
        }
        //将结果输出到数组
        int arr[]=new int[getResult.size()];
        for(int i=0;i<getResult.size();i++){
            arr[i]=getResult.get(i);
        }
        return arr;
    }
    //构造树
    public TreeNode getTree(List<Integer> preList,List<Integer> midList){
        if(midList.isEmpty()){
            return null;
        }
        int rootVal=preList.remove(0);
        TreeNode root=new TreeNode(rootVal);
        int mid=midList.indexOf(rootVal);
        root.left=getTree(preList,midList.subList(0,mid));
        root.right=getTree(preList,midList.subList(mid+1,midList.size()));
        return root;
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型一维数组 先序遍历
     * @param zhongxu int整型一维数组 中序遍历
     * @return int整型一维数组
     */
    public int[] solve (int[] xianxu, int[] zhongxu) {
        TreeNode root =  dfs(0, 0, zhongxu.length - 1, xianxu,zhongxu);
        return TreerightView(root);
    }

    private int[] TreerightView(TreeNode root){
        if(root==null){
            return new int[0];
        }
        Queue<TreeNode> qu = new LinkedList<>();
        ArrayList<Integer> arr = new ArrayList<>();
        qu.add(root);
        while(!qu.isEmpty()){
            int size = qu.size();
            for(int i=0;i<size;i++){
                TreeNode cur = qu.poll();
                if(i==size-1) arr.add(cur.val);
                if(cur.left!=null) qu.add(cur.left);
                if(cur.right!=null) qu.add(cur.right);
            }
        }
        // //将ArrayList转为int[]
        // int arrsize = arr.size();
        // int[] arrint = new int[arrsize];
        // for(int i=0;i<arrsize;i++){
        //     arrint[i]=arr.get(i).intValue();
        // }
        // return arrint;

        return arr.stream().mapToInt(Integer::intValue).toArray();

    }

    private TreeNode dfs(int preStart, int vinStart, int vinEnd, 
    int[] preOrder,int[] vinOrder) {
        //元素为空//位置不对
        if (preStart > preOrder.length - 1 || vinStart > vinEnd) {
            return null;
        }
        //从先序遍历首元素构建结点
        TreeNode root = new TreeNode(preOrder[preStart]);
        int index = 0;
        //查找中序遍历结果位置
        for (int i = vinStart; i <= vinEnd; i++ ) {
            if (vinOrder[i] == root.val) {
                index = i;
                break;
            }
        }
        //左结点为先序下一个结点,且该节点位于index左侧
        root.left = dfs(preStart + 1, vinStart, index - 1, preOrder, vinOrder);
        //右结点先序位置为当前结点先序位置+(当前结点左子树数量(当前中序位置-中序开始位置)+当前结点)
        root.right = dfs(preStart + index - vinStart + 1, index + 1, vinEnd, preOrder,vinOrder);
        return root;
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型一维数组 先序遍历
     * @param zhongxu int整型一维数组 中序遍历
     * @return int整型一维数组
     */
    public int[] solve (int[] xianxu, int[] zhongxu) {
        // write code here
        TreeNode root = build(xianxu, 0, xianxu.length - 1, zhongxu, 0,
                              zhongxu.length - 1);
        //找到右视图
        LinkedList<TreeNode> qu = new LinkedList<TreeNode>();
        qu.add(root);
        List<Integer> list = new ArrayList<Integer>();
        while (!qu.isEmpty()) {
            int size = qu.size();
            list.add(qu.get(size-1).val);
            while (size > 0) {
                size--;
                TreeNode temp = qu.remove();
                if (temp.left != null) {
                    qu.add(temp.left);
                }
                if (temp.right != null) {
                    qu.add(temp.right);
                }
            }
        }
        //转换list为数组arr
        int[] arr = new int[list.size()];
        int index = 0;
        for (Integer item : list) {
            arr[index++] = item;
        }
        //返回结果
        return arr;

    }

    TreeNode build(int[] preOrder, int preStart, int preEnd, int[] inOrder,
                   int inStart, int inEnd) {
        if (preStart > preEnd) {
            return null;
        }
        int rootVal = preOrder[preStart];
        //找到中序中rootVal的位置index
        int index = inStart;
        while (index < inEnd) {
            if (inOrder[index] == rootVal) {
                break;
            }
            index++;
        }
        //确定中序左子树的长度leftsize
        int leftsize = index - inStart;

        TreeNode root = new TreeNode(rootVal);
        root.left = build(preOrder, preStart + 1, preStart + leftsize, inOrder, inStart,
                          index - 1);
        root.right = build(preOrder, preStart + leftsize + 1, preEnd, inOrder,
                           index + 1, inEnd);

        return root;
    }
}

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型一维数组 先序遍历
     * @param zhongxu int整型一维数组 中序遍历
     * @return int整型一维数组
     */
    List<Integer> arrayList = new ArrayList();
    public int getRootIndexInOrder(int[] xianxu, int[] zhongxu) {
        for (int i = 0; i < zhongxu.length; i++) {
            if (xianxu[0] == zhongxu[i]) return i;
        }
        return -1;
    }

    public TreeNode getRightTree(int[] xianxu, int[] zhongxu) {
        // write code here
        if (xianxu == null || xianxu.length == 0) return null;
        int preLength = xianxu.length;
        int inOrderLength = zhongxu.length;
        // 创建树根
        TreeNode root = new TreeNode(xianxu[0]);

        int index = getRootIndexInOrder(xianxu, zhongxu);
        // 先序：[1,2,4,5,3]
        // 中序：[4,2,5,1,3]
        root.left = getRightTree(
                        Arrays.copyOfRange(xianxu, 1, index + 1),
                        Arrays.copyOfRange(zhongxu, 0, index)
                    );
        root.right = getRightTree(
                         Arrays.copyOfRange(xianxu, index + 1, preLength),
                         Arrays.copyOfRange(zhongxu, index + 1, inOrderLength)
                     );
        return root;
    }

    public void getRightViewList(TreeNode root) {
        if (root == null) return;
        Queue<TreeNode> queue = new LinkedList();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- != 0) {
                TreeNode poll = queue.poll();
                if (poll.left != null) {
                    queue.add(poll.left);
                }
                if (poll.right != null) {
                    queue.add(poll.right);
                }
                if (size == 0) arrayList.add(poll.val);
            }
        }
    }
    public int[] solve (int[] xianxu, int[] zhongxu) {
        TreeNode root = getRightTree(xianxu, zhongxu);
        getRightViewList(root);
        return arrayList.stream().mapToInt(Integer::intValue).toArray();
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型一维数组 先序遍历
     * @param zhongxu int整型一维数组 中序遍历
     * @return int整型一维数组
     */
    public int[] solve (int[] xianxu, int[] zhongxu) {
        // write code here
        //1、重建树
        TreeNode root = rebuildTree(xianxu, zhongxu);
        //2、右视图
        List<Integer> list = new ArrayList<>();
        rightview(root, 0, list);
        //3、将list变为int[]
        int[] ans = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            ans[i] = list.get(i);
        }
        return ans;

    }
    private TreeNode rebuildTree(int[] xianxu, int[] zhongxu) {
        int pl = xianxu.length;
        int ml = zhongxu.length;
        //分治算法
        if (pl == 0 || ml == 0) return null;
        TreeNode node = new TreeNode(xianxu[0]);//根
        //找到中序根中对应的第一个序号
        for (int i = 0; i < ml ; i++) {
            if (xianxu[0] == zhongxu[i]) {
                node.left = rebuildTree(Arrays.copyOfRange(xianxu, 1, i + 1),
                                        Arrays.copyOfRange(zhongxu, 0, i));
                node.right = rebuildTree(Arrays.copyOfRange(xianxu, i + 1, pl),
                                         Arrays.copyOfRange(zhongxu, i + 1, ml));
                break;
            }
        }
        return node;
    }

    private void rightview(TreeNode root, int height, List<Integer> list) {
        if (root == null) return ;
        if (height == list.size()) list.add(0); //每层初始化为0
        list.set(height++,
                 root.val); //按照从左到右的顺序，某个高度的最后一个值必为右
        rightview(root.left, height, list);
        rightview(root.right, height, list);
    }

}