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

class Solution {
  private:
    struct TreeNode {
        int val;
        TreeNode* left{};
        TreeNode* right{};
        TreeNode(int x) : val(x) {}
    };

    // 恢复二叉树的辅助函数
    TreeNode* buildTreeHelper(vector<int>& preorder, int preStart, int preEnd,
                              vector<int>& inorder, int inStart, int inEnd,
                              unordered_map<int, int>& inMap) {
        if (preStart > preEnd || inStart > inEnd) return nullptr;

        auto* root = new TreeNode(preorder[preStart]);
        int inRoot = inMap[root->val];
        int numsLeft = inRoot - inStart;

        root->left = buildTreeHelper(preorder, preStart + 1, preStart + numsLeft,
                                     inorder, inStart, inRoot - 1, inMap);
        root->right = buildTreeHelper(preorder, preStart + numsLeft + 1, preEnd,
                                      inorder, inRoot + 1, inEnd, inMap);

        return root;
    }

    // 根据前序遍历和中序遍历恢复二叉树
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        unordered_map<int, int> inMap;
        for (int i = 0; i < inorder.size(); i++) {
            inMap[inorder[i]] = i;
        }
        return buildTreeHelper(preorder, 0, preorder.size() - 1, inorder, 0,
                               inorder.size() - 1, inMap);
    }

    // 获取右视图
    vector<int> rightSideView(TreeNode* root) {
        vector<int> view;
        if (!root) return view;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode* node = q.front();
                q.pop();
                if (i == size - 1) view.push_back(node->val); // Add the last node of each level
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
        }
        return view;
    }

  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求二叉树的右视图
     * @param preOrder int整型vector 先序遍历
     * @param inOrder int整型vector 中序遍历
     * @return int整型vector
     */
    vector<int> solve(vector<int>& preOrder, vector<int>& inOrder) {
        // write code here
        TreeNode* root = buildTree(preOrder, inOrder);
        return rightSideView(root);
    }
};