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

import java.util.*;

public class Solution {
    public int[] solve (int[] xianxu, int[] zhongxu) {
        // 重建二叉树
        TreeNode tree = reConstructBinaryTree(xianxu, zhongxu);
        List<Integer> rightResult = new ArrayList<>();
        getRightResult(tree, rightResult, 0); // 获取右视图
        return rightResult.stream().mapToInt(Integer::intValue).toArray();
    }

    /**
     * 重建二叉树
     * @param pre 先序遍历
     * @param vin 中序遍历
     */
    private TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
        if(pre.length==0 || vin.length==0) return null;
        TreeNode curNode = new TreeNode(pre[0]); // 第一个前序节点为根节点
        for (int i = 0; i < vin.length; i++) {
            if(pre[0] == vin[i]){ // 在中序序列中找到该值
                // Arrays.copyOfRange(arr, l, r)=arr[l,r)左闭右开，包含arr[l]，不包含arr[r]
                // 对于左子树，pre[1,i]为前序序列，  vin[0,i-1]为中序序列
                //          pre[1,i]=pre[1,i+1)；vin[0,i-1]=>vin[0,i)
                curNode.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i+1), Arrays.copyOfRange(vin, 0, i));
                // 对于右子树，pre[i+1,last]为前序序列，        vin[i+1,last]为中序序列
                //         pre[i+1,last]=pre[i+1,length-1)；vin[i+1,last]=>vin[i+1,length-1)
                curNode.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i+1, pre.length), Arrays.copyOfRange(vin, i + 1, vin.length));
            }
        }
        return curNode;
    }

    /**
     * 获取右视图
     */
    private void getRightResult(TreeNode tree, List<Integer> result, int height){
        if(tree==null) return;
        if(result.size()<=height) { // 该层已被访问过，不再记录该层的值
            result.add(tree.val);
        }
        getRightResult(tree.right, result, height + 1); // 先访问右子树
        getRightResult(tree.left, result, height + 1); // 再访问左子树
    }
}