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

题目描述
请根据二叉树的前序遍历，中序遍历恢复二叉树，并打印出二叉树的右视图

解法

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型vector 先序遍历
     * @param zhongxu int整型vector 中序遍历
     * @return int整型vector
     */
    //解法：二叉树重构+输出树的右视图
    // 时间 O（n）, 空间 O（n）
    vector<int> solve(vector<int>& xianxu, vector<int>& zhongxu) {
        TreeNode* root = buildTree(xianxu, zhongxu);
        vector<int> ans = treeRightView(root);
        return ans;
    }
    // 打印 树右视图
    // 层序遍历， 存储最右边的节点
    // 时间O（N），空间 O（N）
    vector<int> treeRightView(TreeNode* root) {
        vector<int> ans;
        if (root == nullptr) return ans;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int levelSize = q.size();
            for (int i = 0; i < levelSize; i++) {
                TreeNode* curNode = q.front();
                q.pop();
                if (curNode->left) q.push(curNode->left);
                if (curNode->right) q.push(curNode->right);
                if (i == levelSize - 1) {
                    ans.push_back(curNode->val);
                }
            }
        }
        return ans;
    }

    // 根据 前序+中序 构建二叉树
    TreeNode* buildTree(vector<int>& xianxu, vector<int>& zhongxu) {
        unordered_map<int, int> valInMap;
        for (int i = 0; i < zhongxu.size(); i++) {
            valInMap[zhongxu[i]] = i;
        }
        TreeNode * tree = buildTreeRec(xianxu, zhongxu, 0, xianxu.size() - 1, 
                                       0, zhongxu.size() - 1, valInMap);
        return tree;
    }
    TreeNode* buildTreeRec(vector<int>& xianxu, vector<int>& zhongxu,
                           int preS, int preE, int inS, int inE, unordered_map<int,int> valInMap) {
        //终止条件
        if (preS > preE || inS > inE) return nullptr;

        //处理
        //构建当前节点
        int rootVal = xianxu[preS];
        TreeNode* root = new TreeNode(rootVal);

        //构建左右子树
        int rootInIdx = valInMap[rootVal];
        int leftTreeSize = rootInIdx - inS;
        root->left = buildTreeRec(xianxu, zhongxu, preS + 1, preS + leftTreeSize, inS, rootInIdx - 1, valInMap);
        root->right = buildTreeRec(xianxu, zhongxu,  preS + leftTreeSize + 1, preE, rootInIdx + 1, inE, valInMap);

        return root;
    }