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

#include <iterator>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型vector 先序遍历
     * @param zhongxu int整型vector 中序遍历
     * @return int整型vector
     */
    vector<int> ans;
    TreeNode* create(vector<int> pre, int l1, int r1, vector<int> in, int l2, int r2) {
        int mid;
        for (int i = 0; i < in.size(); i++) {
            if (in[i] == pre[l1]) {
                mid = i;
                break;
            }
        }
        TreeNode* node = new TreeNode(pre[l1]);
        int llen = mid - l2;
        int rlen = r2 - mid;
        if (llen > 0) {
            node->left = create(pre, l1 + 1, l1 + llen, in, l2, l2 + llen - 1);
        }
        else node->left = nullptr;
        if (rlen > 0) {
            node->right = create(pre, l1 + 1 + llen, r2, in, l2 + llen + 1, r2);
        }
        else node->right = nullptr;
        return node;
    }
    void find(TreeNode* T){
        queue<TreeNode*> Q;
        if(T){
            Q.push(T);
        } 
      // cout<<T->left->left->val;
        while(!empty(Q)){
            int size=Q.size();
            for(int i=0;i<size;i++){
                T=Q.front();
                Q.pop();
                if(T->left) Q.push(T->left);
                if(T->right) Q.push(T->right);
                if(i==size-1){
                    ans.push_back(T->val);
                }
            }
        }
    }
    vector<int> solve(vector<int>& xianxu, vector<int>& zhongxu) {
        // write code here
        if(xianxu.size()==0)  return ans;
       find( create(xianxu,0,xianxu.size()-1,zhongxu,0,zhongxu.size()-1));
        return ans;
    }
};