[数据结构与算法]NC136 输出二叉树的右视图

NC136 输出二叉树的右视图

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

示例1
输入：
[1,2,4,5,3],[4,2,5,1,3]
复制
返回值：
[1,3,5]

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型一维数组 先序遍历
     * @param zhongxu int整型一维数组 中序遍历
     * @return int整型一维数组
     */
    public int[] solve (int[] xianxu, int[] zhongxu) {
        // write code here
        if(xianxu == null){
            return null ;
        }
        TreeNode root = reBuild(xianxu, zhongxu);
        return printRight(root);
    }
     public TreeNode reBuild(int[] pre, int[] in){
        if(pre == null || pre.length == 0){
            return null;
        }
       
        TreeNode root = new TreeNode(pre[0]) ;
        for(int i = 0 ; i < in.length; i++){
            if(in[i] == root.val ){
                root.left = reBuild(Arrays.copyOfRange(pre,1,i+1),
                            Arrays.copyOfRange(in,0, i));
                root.right = reBuild(Arrays.copyOfRange(pre,i+1,pre.length),
                            Arrays.copyOfRange(in,i+1, in.length));
            }
        }
        return root;
    }
    public int[] printRight(TreeNode root){
        if(root == null){
            return null;
        }
        List<Integer> list = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i = 0; i < size; i++){
                TreeNode node = queue.poll();
                if(i == size - 1){
                    list.add(node.val);
                }
                if(node.left != null){
                    queue.offer(node.left);
                }
                if(node.right != null){
                    queue.offer(node.right);
                }
            }
        }
        int[] result = new int[list.size()];
        int index = 0;
        for(int num : list){
            result[index++] = num;
        }
        return result;
    }
}