指针二叉树中序先序转后序
时间: 2023-10-17 17:24:29 浏览: 32
对于指针二叉树,我们可以使用递归的方式来实现中序先序转后序。
具体步骤如下:
1. 如果当前节点为空,则返回空字符串。
2. 递归遍历当前节点的左子树,得到左子树的后序遍历字符串。
3. 递归遍历当前节点的右子树,得到右子树的后序遍历字符串。
4. 将当前节点的值加入后序遍历字符串中。
5. 返回左子树后序遍历字符串 + 右子树后序遍历字符串 + 当前节点的值。
代码实现如下:
```C++
#include <iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
string inorder_preorder_to_postorder(TreeNode* root) {
if (root == nullptr) {
return "";
}
string left_str = inorder_preorder_to_postorder(root->left);
string right_str = inorder_preorder_to_postorder(root->right);
string cur_str = to_string(root->val);
return left_str + right_str + cur_str;
}
int main() {
// 构建二叉树
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
root->right->left = new TreeNode(6);
root->right->right = new TreeNode(7);
// 中序遍历:4 2 5 1 6 3 7
// 先序遍历:1 2 4 5 3 6 7
// 后序遍历:4 5 2 6 7 3 1
cout << "后序遍历结果为:" << inorder_preorder_to_postorder(root) << endl;
return 0;
}
```
输出结果为:
```
后序遍历结果为:4526731
```