题解 | #输出二叉树的右视图#构造二叉树+层次遍历

主要思想：

• 根据前序遍历和中序遍历构造二叉树
• 对构建的二叉树进行层次遍历
• 层次遍历过程中对每一层的最后一个Node上的值保存到list中，这样list中存储的就是最终该棵树的右视图

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型一维数组 先序遍历
     * @param zhongxu int整型一维数组 中序遍历
     * @return int整型一维数组
     */
    public int[] solve (int[] xianxu, int[] zhongxu) {
        // write code here
        TreeNode root = build(xianxu, zhongxu);
        List<Integer> list = new LinkedList<>();
        Deque<TreeNode> deque = new ArrayDeque<>();
        deque.offer(root);
        int levelCount = 1;
        while(!deque.isEmpty()) {
            list.add(deque.peekLast().val);
            while(levelCount-- > 0) {
                TreeNode node = deque.pollFirst();
                if(node.left != null) {
                    deque.offer(node.left);
                }
                if(node.right != null) {
                    deque.offer(node.right);
                }
            }
            levelCount = deque.size();
        }
        int[] arr = new int[list.size()];
        for(int i = 0; i < arr.length; i++) {
            arr[i] = list.get(i);
        }
        return arr;
    }
    public TreeNode build(int[] pre, int[] vin) {
        int n = pre.length;
        int m = vin.length;
        if(n == 0 || m == 0) {
            return null;
        }
        // 构造根节点
        TreeNode root = new TreeNode(pre[0]);
        // 找到中序遍历中根节点的左右子树
        for(int i = 0; i < vin.length; i++) {
            if(vin[i] == pre[0]) {
                root.left = build(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(vin, 0, i));
                root.right = build(Arrays.copyOfRange(pre, i + 1, pre.length), Arrays.copyOfRange(vin, i + 1, vin.length));
                break;
            }
            
        }
        return root;
    }
}