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

1.根据前序和中序构建对应的二叉树 2.输出其右视图，利用层序遍历的方式

import java.util.*;


public class Solution {
    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(){}
        TreeNode(int val){
            this.val = val;
        }
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型一维数组 先序遍历    中 左 右
     * @param zhongxu int整型一维数组 中序遍历   左 中 右
     * @return int整型一维数组
     */
    public int[] solve (int[] xianxu, int[] zhongxu) {
        // write code here
        TreeNode root = buildTree(xianxu, 0, xianxu.length, zhongxu, 0, zhongxu.length);
        List<Integer> ansList = getRightView(root);
        return ansList.stream().mapToInt(Integer::intValue).toArray();
    }
    
    public TreeNode buildTree(int[] xianxu, int xleft, int xright, int[] zhongxu, int zleft, int zright){
        if(zleft >= zright)    return null;
        if(zleft + 1 == zright)    return new TreeNode(zhongxu[zleft]);
        TreeNode node = new TreeNode(xianxu[xleft]);
        int k = zleft;
        for(int i = zleft; i < zright; i++){
            if(zhongxu[i] == xianxu[xleft]){
                k = i;
                break;
            }
        }
        node.left = buildTree(xianxu, xleft + 1, xleft + 1 + (k - zleft), zhongxu, zleft, k);
        node.right = buildTree(xianxu, xleft + 1 + (k - zleft), xright, zhongxu, k + 1, zright);
        return node;
    }
    
    public List<Integer> getRightView(TreeNode root){
        Queue<TreeNode> queue = new LinkedList<>();
        List<Integer> list = new ArrayList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            List<Integer> tmp = new ArrayList<>();
            int size = queue.size();
            for(int i = 0; i < size; i++){
                TreeNode node = queue.poll();
                tmp.add(node.val);
                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
            }
            list.add(tmp.get(tmp.size() - 1));
        }
        return list;
    }  
}