输入先序遍历和中序遍历，输出后序遍历，打印出二叉树，用递归做，c++版

Question

如题所述

Answer 1

//先序遍历
#include <iostream>
using namespace std;
struct TreeNode
{
int val;
TreeNode *left, *right;
};
//先序遍历
void PreorderTraversal(TreeNode* root) {
if (!root) return;
cout << root->val << endl;
if (root->left) 
PreorderTraversal(root->left);
if (root->right)
PreorderTraversal(root->right);
}

//中序遍历
void InorderTraversal (TreeNode* root){
if (!root) return;
if (root->left) 
InorderTraversal(root->left);
cout << root->val << endl;
if (root->right)
InorderTraversal(root->right);
}
//后序遍历
void PostorderTraversal (TreeNode* root){
if (!root) return;
if (root->left) 
InorderTraversal(root->left);
if (root->right)
InorderTraversal(root->right);
cout << root->val << endl;
}
int main()
{
...
}

追问

不对啊

追答

先序遍历就是中->左->右, 访问根结点的操作发生在遍历左右子结点之前;
中序遍历就是左->中->右, 访问根结点的操作发生在遍历左右子结点之间;
后续遍历就是左->右->中, 访问根结点的操作发生在遍历左右子结点之后.

本回答被网友采纳