二叉树右视图

搞了半天，写个题解。

本题总体可拆分为两部分：
① 根据先序、中序遍历重构二叉树
② 层序遍历二叉树输出每层最右侧元素

逐个分析下。
一、重构

1. 先序确定根节点，中序确定左右子树；

2. 左右子树又可以继续拆分，继续确定子树的根节点及左右子；
   上代码：

   public TreeNode reBuild (int[] preOrder, int[] inOrder) {
   
        if (preOrder == null || preOrder.length == 0) return null;
   
        int val = preOrder[0], pos = 0, len = preOrder.length;
        TreeNode root = new TreeNode(val);
   
        // 找到中序数组中根节点位置
        for(; pos < len; pos++){
            if (inOrder[pos] == val) break;
        }
        // 左右子树继续拆分，递归重构
        // 此处 Arrays.copyOfRange 方法起点为 len 不抛异常，返回[]，对应递归结束条件。
        root.left = reBuild(Arrays.copyOfRange(preOrder, 1, pos + 1),
                Arrays.copyOfRange(inOrder, 0, pos));
        root.right = reBuild(Arrays.copyOfRange(preOrder, pos + 1, len),
                Arrays.copyOfRange(inOrder, pos + 1, len));
   
        return root;
    }

二、右视图

1. 原理同层序遍历，广度优先（bfs）；

2. 队列存储结点，左先右后。List 记录每层最后出队的元素（每层最右，即为右视图）；
   上代码：

   public int[] bfs(TreeNode root){
   
        if (root == null) return null;
   
        List<Integer> list = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
   
        for (TreeNode tmp = root; !queue.isEmpty(); ){
            // 此处注意循环中 queue.size() 在变，应事先记录 size--
            for (int size = queue.size(); size > 0; size--){
                tmp = queue.poll();
                if (tmp.left != null) queue.offer(tmp.left);
                if (tmp.right != null) queue.offer(tmp.right);
            }
            // 添加每层最右元素
            list.add(tmp.val);
        }
        return list.stream().mapToInt(Integer::valueOf).toArray();
    }

三、最后两部分合并即为题解：

    public int[] solve (int[] xianxu, int[] zhongxu) {
        TreeNode root = reBuild(xianxu, zhongxu);
        return bfs(root);
    }