题目只给了先序遍历,然后让我们输出对应的中序遍历,同样的,首先根据先序遍历构建二叉树,因为空树是用#号表示出来,所以输入其实就相当于是一棵完全二叉树,则可以唯一确定一颗二叉树,然后我们只需要根据当前的字符是否为#号,来判断是否需要返回nullptr即可:
#include#include using namespace std; int n; string preOrder; struct TreeNode{ char data; struct TreeNode *lchild, *rchild; TreeNode(char c): data(c), lchild(nullptr), rchild(nullptr){} }; TreeNode* Build(){ char ch = preOrder[n++]; //需要首先取出该字符 if(ch == '#') return nullptr; TreeNode *root = new TreeNode(ch); root->lchild = Build(); root->rchild = Build(); return root; } void inOrder(TreeNode *root){ if(root){ inOrder(root->lchild); printf("%c ", root->data); inOrder(root->rchild); } } int main(){ while(cin>>preOrder){ n = 0; TreeNode *root = Build(); inOrder(root); printf("n"); } return 0; }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)