【问题描述】 给定一棵二叉树的先序遍历序列和中序遍历序列，求解： 1、这棵树的后序遍历序列； 2、从这棵树的右侧观察该树，从根节点到叶子节点，依次输出能被观测到的节点序列。用C++实现

【解题思路】

1、根据二叉树的先序遍历和中序遍历序列求解树的后序遍历，可以采用递归的方式进行求解。先序遍历序列的第一个元素为根节点，根据该节点在中序遍历序列中的位置，可以将中序遍历序列划分为左子树和右子树两部分。在先序遍历序列中，根据左子树和右子树的节点个数，也可以将先序遍历序列划分为左子树和右子树两部分。递归地进行该过程，直到序列长度为1时结束递归，返回该节点。

2、从根节点开始，按照右-根-左的顺序遍历树，记录下每个被观测到的节点，即右子树的叶子节点和根节点。采用递归的方式进行求解，对于每个节点，先访问它的右子树，再访问它本身，最后访问它的左子树。

【代码实现】

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

// 定义二叉树节点
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 根据先序遍历和中序遍历序列求解后序遍历序列
vector<int> postorderTraversal(vector<int>& preorder, vector<int>& inorder) {
    unordered_map<int, int> indexMap;
    int n = preorder.size();
    for (int i = 0; i < n; i++) {
        indexMap[inorder[i]] = i;
    }
    vector<int> res;
    function<void(int, int, int, int)> helper = [&](int preLeft, int preRight, int inLeft, int inRight) {
        if (preLeft > preRight) {
            return;
        }
        int rootVal = preorder[preLeft];
        int rootIndex = indexMap[rootVal];
        int leftSize = rootIndex - inLeft;
        int rightSize = inRight - rootIndex;
        helper(preLeft + 1, preLeft + leftSize, inLeft, rootIndex - 1);
        helper(preLeft + leftSize + 1, preRight, rootIndex + 1, inRight);
        res.push_back(rootVal);
    };
    helper(0, n - 1, 0, n - 1);
    return res;
}

// 从右侧观察二叉树，输出节点序列
vector<int> rightSideView(TreeNode* root) {
    vector<int> res;
    function<void(TreeNode*, int)> helper = [&](TreeNode* node, int depth) {
        if (node == nullptr) {
            return;
        }
        if (depth == res.size()) {
            res.push_back(node->val);
        }
        helper(node->right, depth + 1);
        helper(node->left, depth + 1);
    };
    helper(root, 0);
    return res;
}

int main() {
    // 例子：先序遍历序列为[1,2,4,5,3,6]，中序遍历序列为[4,2,5,1,3,6]
    vector<int> preorder{1, 2, 4, 5, 3, 6};
    vector<int> inorder{4, 2, 5, 1, 3, 6};
    vector<int> postorder = postorderTraversal(preorder, inorder);
    cout << "后序遍历序列：";
    for (auto i : postorder) {
        cout << i << " ";
    }
    cout << endl;

    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->right = new TreeNode(4);
    root->right->right = new TreeNode(5);
    vector<int> rightSideViewNodes = rightSideView(root);
    cout << "从右侧观察树，能被观测到的节点序列：";
    for (auto i : rightSideViewNodes) {
        cout << i << " ";
    }
    cout << endl;

    return 0;
}