先建树再层序遍历
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; } }