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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求二叉树的右视图
     * @param preOrder int整型一维数组 先序遍历
     * @param inOrder int整型一维数组 中序遍历
     * @return int整型一维数组
     */
    public int[] solve (int[] preOrder, int[] inOrder) {
        TreeNode root = reBuild(preOrder, inOrder);
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        ArrayList<Integer> lists = new ArrayList<Integer>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- != 0) {
                TreeNode temp = queue.poll();
                if (temp.left != null)
                    queue.offer(temp.left);
                if (temp.right != null)
                    queue.offer(temp.right);
                //最右元素
                if (size == 0)
                    lists.add(temp.val);
            }
        }
        int[] res = new int[lists.size()];
        for (int i = 0; i < lists.size(); i++)
            res[i] = lists.get(i);
        return res;
    }
    private TreeNode reBuild(int[] preOrder, int[] inOrder) {
        if(preOrder.length==0||inOrder.length==0)
            return null;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode root = new TreeNode(preOrder[0]);
        TreeNode cur = root;
        for (int i = 1, j = 0; i < preOrder.length; i++) {
            if (cur.val != inOrder[j]) {
                cur.left = new TreeNode(preOrder[i]);
                stack.push(cur);
                cur = cur.left;
            } else {
                j++;
                while (!stack.isEmpty() && stack.peek().val == inOrder[j]) {
                    cur = stack.pop();
                    j++;
                }
                cur.right = new TreeNode(preOrder[i]);
                cur = cur.right;
            }
        }
        return root;
    }
}