给定⼀个⼆叉树的根节点 root，返回它的 中序 遍历。用C++实现

中序遍历是指，以 root 为根节点，先遍历 root 的左子树，再遍历 root 节点，最后遍历 root 的右子树。用 C 语言实现的话，可以这样： void inOrder(TreeNode *root) {
if (root == NULL)
return;
inOrder(root->left);
printf("%d ", root->val);
inOrder(root->right);
}

相关问题

C++：利用结构体编写一个程序， 在自定义函数中完成下列功能并在主函数进行测试：(1) 由树的先序遍历序列和中序遍历序列创建一棵二叉树。(2) 输出二叉树的后序遍历序列。测试数据：先序遍历序列: ABDGCEF↵中序遍历序列: DGBAECF↵

在C++中，我们可以首先定义一个结构体`Node`表示二叉树的节点，接着实现先序、中序遍历的递归函数以及后序遍历。这里是一个简单的示例：

#include <iostream>
using namespace std;

// 定义二叉树节点结构
struct Node {
    char data;
    Node* left;
    Node* right;
};

// 创建新节点
Node* createNode(char data) {
    Node* newNode = new Node();
    newNode->data = data;
    newNode->left = newNode->right = nullptr;
    return newNode;
}

// 先序遍历 (根 -> 左 -> 右)
void preOrder(Node* node) {
    if (node != nullptr) {
        cout << node->data << " ";
        preOrder(node->left);
        preOrder(node->right);
    }
}

// 中序遍历 (左 -> 根 -> 右)
void inOrder(Node* node) {
    if (node != nullptr) {
        inOrder(node->left);
        cout << node->data << " ";
        inOrder(node->right);
    }
}

// 后序遍历 (左 -> 右 -> 根)
void postOrder(Node* node) {
    if (node != nullptr) {
        postOrder(node->left);
        postOrder(node->right);
        cout << node->data << " ";
    }
}

// 通过先序和中序遍历来构造二叉树
Node* buildTreeFromPreIn(string preStr, string inStr) {
    int preIndex = 0, inIndex = 0;
    Node* root = nullptr, *temp = nullptr;
    
    for (int i = 0; i < inStr.length(); ++i) {
        if (preStr[preIndex] == inStr[i]) { // 找到当前要构建的节点位置
            temp = createNode(inStr[i]);
            root = (root == nullptr ? temp : root->left) = findSubtree(preStr, inStr, preIndex, inIndex);
            ++preIndex;
        } else {
            ++inIndex;
        }
    }
    return root;
}

// 从两个字符串中找到对应的子树
Node* findSubtree(string str1, string str2, int& start1, int& start2) {
    if (start1 >= str1.length()) return nullptr;
    if (start2 >= str2.length()) return nullptr;
    if (str1[start1] == str2[start2]) {
        Node* newNode = createNode(str1[start1]);
        start1++;
        start2++;
        newNode->left = findSubtree(str1, str2, start1, start2);
        newNode->right = findSubtree(str1, str2, start1, start2);
        return newNode;
    } else {
        return start1 < str1.length() ? findSubtree(str1, str2, start1 + 1, start2) : nullptr;
    }
}

int main() {
    string preOrderStr = "ABDGCEF";
    string inOrderStr = "DGBAECF";

    // 构造二叉树
    Node* root = buildTreeFromPreIn(preOrderStr, inOrderStr);

    // 输出二叉树的后序遍历序列
    cout << "后序遍历序列: ";
    postOrder(root);

    return 0;
}

在这个示例中，我们首先定义了`Node`结构体，然后实现了遍历和构建二叉树的相关函数。在`main`函数中，我们使用给定的先序和中序遍历序列来创建树，并最后输出后序遍历序列。

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