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

先构造二叉树，再使用层序遍历取最右侧节点

import java.util.*;

// 构造节点
class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型一维数组 先序遍历
     * @param zhongxu int整型一维数组 中序遍历
     * @return int整型一维数组
     */

    private HashMap<Integer, Integer> map = new HashMap<>();
    ArrayList<Integer> list = new ArrayList<>();

    public int[] solve (int[] qianxu, int[] zhongxu) {
        // write code here
        for (int i = 0; i < zhongxu.length; i++) map.put(zhongxu[i], i);
        TreeNode root = build(qianxu, 0, qianxu.length - 1, 0, zhongxu.length - 1);
        rightView(root);
        int[] res = new int[list.size()];
        for (int i = 0; i < res.length; i++) res[i] = list.get(i);
        return res;
    }

    // 构造二叉树
    public TreeNode build(int[] qianxu, int ps, int pe, int is, int ie) {
        if (ps > pe || is > ie) return null;
        int val = qianxu[ps];
        int id = map.get(val);
        TreeNode root = new TreeNode(val);
        root.left = build(qianxu, ps + 1, ps + id - is, is, id - 1);
        root.right = build(qianxu, ps + id - is + 1, pe, id + 1, ie);
        return root;
    }

    // 层序遍历取最右侧节点
    public void rightView(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        if (root != null) queue.offer(root);
        while (!queue.isEmpty()) {
            int n = queue.size();
            for (int i = 0; i < n; i++) {
                TreeNode node = queue.poll();
                if (i == n - 1) list.add(node.val);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }
    }
}