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

主要知识点：根据前序+中序递归建树，层次遍历二叉树

import java.util.*;

public class Solution {

//根据前序+中序遍历重建二叉树
public TreeNode createByPreMid(int[] pre,int[] mid, int ipre,int imid,int n){
    if(n==0)
        return null;
    TreeNode node = new TreeNode(0);
    node.val = pre[ipre];
    int i=0;
    for(;i<n;++i){
        if(pre[ipre]==mid[imid+i])
            break;
    }
    node.left = createByPreMid(pre,mid,ipre+1,imid,i);
    node.right = createByPreMid(pre,mid,ipre+i+1,imid+i+1,n-i-1);
    return node;
}

//层次遍历
public ArrayList<Integer> levelOrder(TreeNode root){
    ArrayList<Integer> arr = new ArrayList<>();
    Deque<TreeNode> dq = new LinkedList<>();
    dq.offer(root);
    while(!dq.isEmpty()){
        int curSize=dq.size();
        while(curSize-->0){
            TreeNode node = dq.poll();
            if(curSize==0)
                arr.add(node.val);
            if(node.left!=null)  dq.offer(node.left);
            if(node.right!=null) dq.offer(node.right);
        }
    }
    return arr;
}


public int[] solve (int[] xianxu, int[] zhongxu) {
    // write code here
    TreeNode root = createByPreMid(xianxu,zhongxu,0,0,xianxu.length);
    ArrayList<Integer> arr = levelOrder(root);
    int[] res = new int[arr.size()];
    for(int i=0;i<arr.size();++i)
        res[i] = arr.get(i);
    return res;
}

}