import java.util.*; class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } public class Solution { private Map<Integer, Integer> inMap = new HashMap<>(); /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 求二叉树的右视图 * @param preOrder int整型一维数组 先序遍历 * @param inOrder int整型一维数组 中序遍历 * @return int整型一维数组 */ public int[] solve (int[] preOrder, int[] inOrder) { // write code here for (int i = 0; i < inOrder.length; i++) { inMap.put(inOrder[i], i); } TreeNode root = buildTree(preOrder, inOrder, 0 , preOrder.length - 1, 0, inOrder.length - 1); Deque<TreeNode> que = new LinkedList<>(); if (root != null) { que.offer(root); } List<Integer> list = new ArrayList<>(); while (!que.isEmpty()) { list.add(que.peekLast().val); int leng = que.size(); for (int i = 0; i < leng; i++) { TreeNode current = que.poll(); if (current.left != null) { que.offer(current.left); } if (current.right != null) { que.offer(current.right); } } } int[] ans = new int[list.size()]; for (int i = 0; i < ans.length; i++) { ans[i] = list.get(i); } return ans; } private TreeNode buildTree(int[] preOrder, int[] vinOrder, int preStart, int preEnd, int inLeft, int inEnd) { if (preEnd < preStart) { return null; } int current = preOrder[preStart]; TreeNode root = new TreeNode(current); int currentIndex = inMap.get(current); int leftLeng = currentIndex - inLeft; root.left = buildTree(preOrder, vinOrder, preStart + 1, preStart + leftLeng, inLeft, currentIndex - 1); root.right = buildTree(preOrder, vinOrder, preStart + leftLeng + 1, preEnd, currentIndex + 1, inEnd); return root; } }
先重建二叉树,再层序遍历