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

import java.util.HashMap;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     *
     * @param xianxu  int整型一维数组 先序遍历
     * @param zhongxu int整型一维数组 中序遍历
     * @return int整型一维数组
     */
    public int[] solve(int[] xianxu, int[] zhongxu) {
        // write code here
        int n = xianxu.length;
        // 特殊情况考虑
        if (n == 0) {
            return new int[0];
        }
        // map 加速在中序数组中查找当前根节点
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            map.put(zhongxu[i], i);
        }
        int max = 1;
        int[] layer = new int[n];
        recur(xianxu, zhongxu, 0, n - 1, 0, n - 1, map, layer, 1);
        for (int i = 0; i < n; ++i) {
            max = Math.max(max, layer[i]);
        }
        int[] res = new int[max];
        // 先序数组中每个节点的层数记录在layer中，此时直接遍历先序数组把下标较大的数值放到对应层数（返回数组中为层数减一）上
        for (int i = 0; i < n; ++i) {
            res[layer[i] - 1] = xianxu[i];
        }
        return res;
    }

    /**
     * 递归函数recur
     *
     * @param pre   先序数组
     * @param in    中序数组
     * @param p1    当前左子树的先序数组中的左边界
     * @param p2    当前左子树的先序数组中的右边界
     * @param i1    当前右子树的先序数组中的左边界
     * @param i2    当前右子树的先序数组中的右边界
     * @param map   存储中序数组中 数值-下标
     * @param layer 存储先序数组的对应层数
     * @param cur   当前节点的层数
     */
    public void recur(int[] pre, int[] in, int p1, int p2, int i1, int i2, HashMap<Integer, Integer> map, int[] layer, int cur) {
        // 边界条件，取决于后面的边界的取法,如p1,i1的赋值不同这里也会有不同
        if (p1 > p2 || i1 > i2) {
            return;
        }
        // 当前节点在中序数组的下标
        int h = map.get(pre[p1]);
        // 存储当前节点的层数
        layer[p1] = cur;
        // 以当前节点为根节点分别进行左右子树的递归，注意边界的取法影响边界的判断
        recur(pre, in, p1 + 1, p1 + (h - i1), i1, h - 1, map, layer, cur + 1);
        recur(pre, in, p2 - (i2 - h) + 1, p2, h + 1, i2, map, layer, cur + 1);
    }
}