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

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型一维数组 先序遍历
     * @param zhongxu int整型一维数组 中序遍历
     * @return int整型一维数组
     */
     Map<Integer,Integer> map = new HashMap<>();
    public int[] solve (int[] xianxu, int[] zhongxu) {
        // write code here 
        int n = xianxu.length;
        for(int i = 0;i < n;i ++){
            map.put(zhongxu[i],i);
        }
        TreeNode root = dfs(xianxu,zhongxu,0,n-1,0,n-1);
        List<Integer> list = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        int last = -1;
        while(!q.isEmpty()){
            int size = q.size();
            for(int i = 0;i < size;i ++){
                TreeNode node = q.poll();
                last = node.val;
                if(node.left != null){
                    q.offer(node.left);
                }
                if(node.right != null){
                    q.offer(node.right);
                }
            }
            list.add(last);
        }
        int[] nums = new int[list.size()];
        int i = 0;
        for(int l : list){
            nums[i++] = l;
        }
        return nums;
    }
    public TreeNode dfs(int[] pre,int[] vin,int pl,int pr,int vl,int vr){
        if(pl > pr){
            return null;
        }
        int rootVal = pre[pl];
        TreeNode root = new TreeNode(rootVal);
        int size = map.get(rootVal) - vl;
        root.left = dfs(pre,vin,pl+1,pl+size,vl,size-1);
        root.right = dfs(pre,vin,pl+size+1,pr,vl+size+1,vr);
        return root;
        
    }
}