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

通过前序和中序构建二叉树同上一题。
求二叉树的右视图可以用层次遍历，找到每一层的最后一个结点并把它并入结果集。

public class Solution {
    public int[] solve (int[] xianxu, int[] zhongxu) {
        // write code here
        TreeNode root = buildTreeByPreorderAndInorder(xianxu, 0, xianxu.length - 1, zhongxu, 0, zhongxu.length - 1);
        return BFS(root);
        
    }
    
    private int[] BFS(TreeNode root){
        if(root == null){
            return new int[0];
        }
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int currLevelNodeNum = queue.size();
        List<Integer> list = new ArrayList<>();
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            currLevelNodeNum--;
            // 当前层所有结点都已出队，说明该结点为该层最后一个结点
            if(currLevelNodeNum == 0){
                list.add(node.val);
            }
            if(node.left != null){
                queue.offer(node.left);
            }
            if(node.right != null){
                queue.offer(node.right);
            }
            if(currLevelNodeNum == 0){
                currLevelNodeNum = queue.size();
            }
        }
        int[] res = new int[list.size()];
        for(int i = 0; i < list.size(); i++){
            res[i] = list.get(i);
        }
        return res;
    }
    
    private TreeNode buildTreeByPreorderAndInorder(int[] pre, int l1, int r1, int[] vin, int l2, int r2){
        if (l1 > r1 || l2 > r2) {
            return null;
        }
        int i;
        for (i = l2; i <= r2; i++) {
            if (vin[i] == pre[l1]) {
                break;
            }
        }
        TreeNode node = new TreeNode(pre[l1]);
        node.left = buildTreeByPreorderAndInorder(pre, l1 + 1, l1 + i - l2, vin, l2, i - 1);
        node.right = buildTreeByPreorderAndInorder(pre, l1 + i - l2 + 1, r1, vin, i + 1, r2);
        return node;
    }
}