本题要求实现给定的二叉树的三种遍历。 函数接口定义： void Preorder(BiTree T); void Inorder(BiTree T); void Postorder(BiTree T); T是二叉树树根指针，Preorder、Inorder和Postorder分别输出给定二叉树的先序、中序和后序遍历序列，格式为一个空格跟着一个字符。 其中BinTree结构定义如下： typedef char ElemType; typedef struct BiTNode { ElemType data; struct BiTNode *lchild, *rchild; }BiTNode, *BiTree; 裁判测试程序样例： #include <stdio.h> #include <stdlib.h> typedef char ElemType; typedef struct BiTNode { ElemType data; struct BiTNode *lchild, *rchild; }BiTNode, *BiTree; BiTree Create();/* 细节在此不表 */ void Preorder(BiTree T); void Inorder(BiTree T); void Postorder(BiTree T); int main() { BiTree T = Create(); printf("Preorder:"); Preorder(T); printf("\n"); printf("Inorder:"); Inorder(T); printf("\n"); printf("Postorder:"); Postorder(T); printf("\n"); return 0; } /* 你的代码将被嵌在这里 */ 输入样例： 输入为由字母和'#'组成的字符串，代表二叉树的扩展先序序列。例如对于如下二叉树，输入数据： AB#DF##G##C##

题目描述

给定一个二叉树的先序遍历、中序遍历和后序遍历，请分别输出它们的遍历结果。

样例

输入： AB#DF##G##C##
输出： Preorder: A B D F G C
Inorder: D F G B A C
Postorder: G F D B C A

算法1

(递归) $O(n)$

对于一棵二叉树，有三种基本的遍历方式：

- 先序遍历：从根节点开始，先输出根节点，然后遍历左子树，最后遍历右子树。
- 中序遍历：从根节点开始，先遍历左子树，然后输出根节点，最后遍历右子树。
- 后序遍历：从根节点开始，先遍历左子树，然后遍历右子树，最后输出根节点。

对于一棵二叉树，前序遍历的第一个节点就是这棵树的根节点，而且在中序遍历中，根节点把这个序列分成了左右两个子树的序列，因此可以根据这个性质进行递归求解。假设当前树的前序遍历序列为pre，中序遍历序列为in，那么可以通过查找pre[0]在in中的位置pos，即可确定左右子树的大小，从而分别递归求解左右子树的前序遍历和中序遍历，最后得到整棵树的前序遍历和中序遍历。

后序遍历的求解与前序遍历类似，只不过需要注意递归的顺序。对于一棵树，后序遍历的最后一个节点就是这棵树的根节点，因此可以先递归求解左右子树的后序遍历，再输出根节点。

时间复杂度

对于每个节点，每个节点会被遍历一次，因此时间复杂度为$O(n)$。

C++ 代码

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
if(!root) return res;
stack<TreeNode*> s;
s.push(root);
while(!s.empty()) {
auto node = s.top();
s.pop();
res.push_back(node->val);
if(node->right) s.push(node->right);
if(node->left) s.push(node->left);
}
return res;
}

vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> s;
auto node = root;
while(node || !s.empty()) {
while(node) {
s.push(node);
node = node->left;
}
node = s.top();
s.pop();
res.push_back(node->val);
node = node->right;
}
return res;
}

vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
if(!root) return res;
stack<TreeNode*> s1, s2;
s1.push(root);
while(!s1.empty()) {
auto node = s1.top();
s1.pop();
s2.push(node);
if(node->left) s1.push(node->left);
if(node->right) s1.push(node->right);
}
while(!s2.empty()) {
res.push_back(s2.top()->val);
s2.pop();
}
return res;
}
};