题解 | #输出二叉树的右视图# 前序中序后序。层次遍历的综合体，记录下来

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型vector 先序遍历
     * @param zhongxu int整型vector 中序遍历
     * @return int整型vector
     */
    /*
        根据pre和中序获取他人
    */
     struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  };
    unordered_map<int, int>um;
    vector<int>level;

    TreeNode *getRoot(vector<int>& xianxu, int preL, int preR, vector<int>& zhongxu, int inL, int inR) {
        // 判断约束条件
        if(preL > preR || inL > inR) {
            return nullptr;
        }
        // 开始递归
        int pos = um[xianxu[preL]];
        TreeNode *root = new TreeNode(xianxu[preL]);
        // 左子树一共有pos-inL + 1
        root->left = getRoot(xianxu, preL + 1, preL + pos - inL, zhongxu, inL, pos - 1);
        root->right = getRoot(xianxu, preL + pos - inL + 1, preR, zhongxu, pos + 1, inR);
        return root;
    }
    
    void levelOrder(TreeNode *root) {
        if (!root) {
            return;
        }
        queue<TreeNode*> que;
        que.push(root);
        
        while(!que.empty()) {
            int size = que.size();
            while(size--) {
                // 把下一层所有的东西都push到里面
                TreeNode *front = que.front();
                que.pop();
                if (front->left) {
                    que.push(front->left);
                }
                if (front->right) {
                    que.push(front->right);
                }
                if (size == 0) {
                    level.push_back(front->val);
                }
              
            }
        }
    }
    vector<int> solve(vector<int>& xianxu, vector<int>& zhongxu) {
        int len = xianxu.size();
        vector<int>ret;
        if (len == 0) {
            return ret;
        }
        // 将中序存入哈希表中
        for (int i = 0; i < len; i++) {
            um[zhongxu[i]] = i;
        }
        TreeNode *root = getRoot(xianxu, 0, len - 1, zhongxu, 0, len - 1);
        // 后续遍历
        levelOrder(root);
        return level;
    }
};