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

【解决思路】

1、根据先序遍历序列找到根节点，然后在中序遍历序列中找到根节点的位置，根据根节点将中序遍历序列分为左子树和右子树，同时在先序遍历序列中也能得到左子树和右子树的先序遍历序列，递归处理左右子树并输出根节点即可得到后序遍历序列。

2、从根节点开始，先遍历右子树，记录每一层第一个被观测到的节点，最后按照层次遍历的顺序输出这些节点即可。

【代码实现】

相关问题

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

1、根据先序遍历序列和中序遍历序列构建二叉树，然后对二叉树进行后序遍历即可得到后序遍历序列。

具体步骤如下：

1. 在先序遍历序列中找到根节点。
2. 在中序遍历序列中找到根节点的位置，根节点左边的部分为左子树的中序遍历序列，右边的部分为右子树的中序遍历序列。
3. 在先序遍历序列中，根节点后面的部分中，与左子树中序遍历序列长度相同的部分为左子树的先序遍历序列，剩下的为右子树的先序遍历序列。
4. 重复上述步骤，递归构建左子树和右子树，直到叶子节点。
5. 对二叉树进行后序遍历，即可得到后序遍历序列。

2、从右侧观察树，从根节点到叶子节点依次输出能被观测到的节点序列，可以使用层次遍历来实现。

具体步骤如下：

1. 将根节点入队列。
2. 从队列中取出节点，将其左右子节点入队列，并记录该节点的值。
3. 重复上述步骤，直到队列为空。
4. 在输出节点值时，只输出每一层的最右侧节点的值，即可得到从右侧观察树时能被观测到的节点序列。

【问题描述】 给定一棵二叉树的先序遍历序列和中序遍历序列，求解： 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;
}