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

import java.util.*;


class Node {
    int val ;
    Node left ;
    Node right ;
    Node() {}
    Node(int val) {this.val = val ;}
}
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型一维数组 先序遍历
     * @param zhongxu int整型一维数组 中序遍历
     * @return int整型一维数组
     */
    public int[] solve (int[] xianxu, int[] zhongxu) {
        //创建二叉树
        Node head = createTree(xianxu , zhongxu , 0 , 0 , xianxu.length) ;
        //求右视图（层序遍历）
        ArrayList<Integer> rightViewList = new ArrayList<>() ;
        Queue<Node> que = new LinkedList<>() ;
        que.offer(head) ;
        while(!que.isEmpty()) {
            //每一层的节点数
            int cur_row_len = que.size() ;
            for(int i = 0 ; i < cur_row_len ; i ++) {
                Node tmp = que.poll() ;
                //将每层最后一个节点加入右视图中
                if(i == cur_row_len - 1) rightViewList.add(tmp.val) ;
                if(tmp.left != null) que.offer(tmp.left) ;
                if(tmp.right != null) que.offer(tmp.right) ;
            }
        }
        int [] res = new int[rightViewList.size()] ;
        for(int i = 0 ; i < res.length ; i ++) {
            res[i] = rightViewList.get(i) ;
        }
        return res ;
    }
    //创建二叉树
    public Node createTree(int[] pre , int[] in , int preIdx , int inIdx , int len) {
        if(len == 0) return null ;
        Node root = new Node(pre[preIdx]) ;
        //寻找root在中序遍历序列中的位置
        int i = inIdx ;
        for(; i < inIdx + len ; i ++) {
            if(in[i] == root.val) break ;
        }
        int l_len = i - inIdx ;
        int r_len = len - l_len - 1 ;
        root.left = createTree(pre , in , preIdx + 1 , inIdx , l_len) ;
        root.right = createTree(pre , in , preIdx + l_len + 1 , i + 1 , r_len) ;
        return root ;
    }
}