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

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型一维数组 先序遍历
     * @param zhongxu int整型一维数组 中序遍历
     * @return int整型一维数组
     */
    public int[] solve (int[] preorder, int[] inorder) {
        // write code here
        if (preorder == null || preorder.length < 1 || inorder == null || inorder.length < 1) {
            return new int[0];
        }
        TreeNode root = rebuild(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
        LinkedList<TreeNode> queue = new LinkedList<>();
        TreeNode cur = root;
        queue.offer(cur);
        List<Integer> list = new ArrayList<>();
        while (!queue.isEmpty()) {
            int size = queue.size();
            list.add(queue.peekLast().val);
            for (int i = 0; i < size; i++) {
                cur = queue.poll();
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
        }
        int[] res = new int[list.size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = list.get(i);
        }
        return res;
    }
    
    public TreeNode rebuild(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
        if (preStart < 0 || inStart < 0 || preStart > preEnd || inStart > inEnd) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[preStart]);
        
        int index = 0;
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == root.val) {
                index = i;
                break;
            }
        }
        int leftLen = index - inStart;
        int rightLen = inEnd - index;
        root.left = rebuild(preorder, preStart + 1, leftLen + preStart, inorder, inStart, index - 1);
        root.right = rebuild(preorder, leftLen + preStart + 1, preEnd, inorder, index + 1, inEnd);
        return root;
    }
    
    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
        
        public TreeNode(int val) {
            this.val = val;
        }
    }
}