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

先建树再层序遍历

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求二叉树的右视图
     * @param preOrder int整型一维数组 先序遍历
     * @param inOrder int整型一维数组 中序遍历
     * @return int整型一维数组
     */
    public int[] solve (int[] preOrder, int[] inOrder) {
        // write code here
        int[] res = new int[] {};
        TreeNode root = build(preOrder, inOrder, 0, preOrder.length - 1, 0,
                              preOrder.length - 1);
        ArrayList<Integer> resList = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            int curLineSize = q.size();
            for (int i = 0; i < curLineSize; i++) {
                TreeNode curNode = q.poll();
                if (curNode.left != null) q.offer(curNode.left);
                if (curNode.right != null) q.offer(curNode.right);
                if (i == curLineSize - 1) resList.add(curNode.val);
            }
        }
        res = new int[resList.size()];
        for (int i = 0; i < resList.size(); i++) res[i] = resList.get(i);
        return res;
    }

    public TreeNode build(int[] preOrder, int[] inOrder, int preL, int preR,
                          int inL, int inR) {
        TreeNode root = new TreeNode(preOrder[preL]);
        //找到preOrder[preL]在中序的位置
        int mid = inL;
        for (int idx = inL; idx <= inR; idx++) {
            if (inOrder[idx] == preOrder[preL]) {
                mid = idx;
                break;
            }
        }
        //左子树的序列长度为mid-inL
        if (inL <= mid - 1) {
            root.left = build(preOrder, inOrder, preL + 1, preL + mid - inL, inL,
                              mid - 1);
        }
        //右子树的序列长度为inR-mid
        if (mid + 1 <= inR) {
            root.right = build(preOrder, inOrder, preL + 1 + mid - inL, preR, mid + 1,
                               inR);
        }
        return root;
    }
}