代码思路是:由先序和中序创建二叉树,再求其后序序列
但是不知道那点有问题?
#include<iostream>
#include<string>
using namespace std;
string pres,ins;
struct node{
char data;
node*lchild;
node*rchild;
};
node*create(string pres,int i,string ins,int j,int n)
{
if(n<=0)return NULL;
char d=pres[i];
node * b=new node(d);
int p=j;
while(ins[p]!=d)p++;
int k=p-j;
b->lchild=creat(pres,i+1,ins,j,k);
b->rchild=creat(pres,i+k+1,ins,p+1,n-k-1);
return b;
}
void postorder(node*b){
if(b!=NULL)
{
postorder(b->lchild);
postorder(b->rchild);
cout<<b->data;
}
}
int main(){
while(cin>>pres&&cin>>ins){
int n=pres.size();
node*b=creat(pres,0,ins,0,n);
postorder(b);
cout<<endl;
}
return 0;
}
struct node 里面加一个构造函数
node(char c) :data(c) {
lchild=nullptr;
rchild=nullptr;
}
创建是create,你写的是creat
/struct TreeNode {
int val;
struct TreeNode left;
struct TreeNode right;
TreeNode(int x) : val(x), left(NULL), right(NULL) { }
};/
class Solution {
public:
TreeNode Convert(TreeNode pRootOfTree)
{
if(!pRootOfTree)
{
return NULL;
}
vector<TreeNode*> V1; //用于存放中序遍历的节点。
InOrder(pRootOfTree, V1);
int i;
for(i = 1;i<V1.size();i++)
{
V1[i-1]->right = V1[i];
V1[i]->left = V1[i-1];
}
return V1[0];
}
void InOrder(TreeNode* Root, vector<TreeNode*> &V)
{
if(!Root)
{
return;
}
if(Root->left)
InOrder(Root->left,V);
V.push_back(Root);
if(Root->right)
InOrder(Root->right, V);
}
};