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

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
private:
    unordered_map<int, int> vin_rd;
    vector<int> res;
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型vector 先序遍历
     * @param zhongxu int整型vector 中序遍历
     * @return int整型vector
     */
    vector<int> solve(vector<int>& xianxu, vector<int>& zhongxu) {
        // write code here
        TreeNode* root = reConstructBinaryTree(xianxu, zhongxu);
        cal(root);
        return res;
    }
    
    void cal(TreeNode* root){
        queue<TreeNode*> Q;
        Q.push(root);
        
        while(!Q.empty()){
            int cur_size = Q.size();
            for(int i=0; i<cur_size; i++){
                auto node = Q.front();
                Q.pop();
                if(node->left) Q.push(node->left);
                if(node->right) Q.push(node->right);
                if(i == cur_size-1){
                    res.push_back(node->val);
                }
            }
        }
    }
    
    TreeNode* reConstructBinaryTree(vector<int>& pre,vector<int>& vin) {
        if(pre.size() == 0){
            return nullptr;
        }
         
        for(int i=0; i<vin.size(); i++){
            vin_rd[vin[i]] = i;
        }
         
        return create(pre, vin, 0, pre.size()-1, 0, vin.size()-1);
    }
     
    TreeNode* create(vector<int>& pre,vector<int>& vin, int a, int b, int c, int d){
        if(a > b){
            return nullptr;
        }
         
        TreeNode* root = new TreeNode(0);
        root->val = pre[a];
         
        int index = vin_rd[pre[a]];
        root->left = create(pre, vin, a+1, a+index-c, c, index-1);
        root->right = create(pre, vin, a+index-c+1, b, index+1, d);
        return root;
    }
    
};