PreOrder InOrder to Create BT
碰到二叉树问题，我非常喜欢用递归来解决，这次设计递归参数出了问题，例如Pre In->BT, 找到的root 的index是In中的index，因此Pre的要根据保持和In调用左(右)子树部分
和他的一样多个结点来计算对应的start end index，另外i已经是绝对位置了，不需要再在start基础上进行偏移，也是没有想清楚犯的错误。细节部分题解先留着。
Pre In 构建BT
TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
TreeNode* root=buildTree1(preorder,inorder,0,preorder.size()-1,0,inorder.size()-1);
return root;
}
TreeNode *buildTree1(vector<int> &preorder, vector<int> &inorder, int prestart,int preend, int instart, int inend)
{
if(preend<=preorder.size() -1 &&prestart>=0 && inend<=inorder.size() -1 &&instart>=0 && prestart<=preend && instart<=inend)
{
TreeNode* root=new TreeNode(preorder[prestart]);
int i;
for(i=instart;i<=inend;i++)
{
if(inorder[i]==preorder[prestart])
break;
}
root->left=buildTree1(preorder,inorder,prestart+1, prestart+i-instart, instart,i-1);
root->right=buildTree1(preorder,inorder, preend+i+1-inend, preend,i+1,inend);
return root;
}
else
return NULL;
}
In Post 构建BT
TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
TreeNode* root=buildTree1(inorder,postorder,0,inorder.size()-1,0,postorder.size()-1);
return root;
}
TreeNode *buildTree1(vector<int> &inorder, vector<int> &postorder, int instart,int inend, int poststart, int postend)
{
if(inend<=inorder.size() -1 &&instart>=0 && postend<=postorder.size() -1 &&poststart>=0 && instart<=inend && poststart<=postend)
{
TreeNode* root=new TreeNode(postorder[postend]);
int i;
for(i=instart;i<=inend;i++)
{
if(inorder[i]==postorder[postend])
break;
}//i inorder index
root->left=buildTree1(inorder,postorder,instart,i-1, poststart,i+poststart-instart-1);
root->right=buildTree1(inorder,postorder,i+1,inend,/*i+poststart-instarti+postend-inend ,postend-1);//sunny
return root;
}
else
return NULL;
}
今天hihocode再写的时候，不会遇到之前相对位置错误的情况了，然后还练了下postorder，发现有个地方记错了，就是如果pop的话，表示孩子都便利完了，后面不能再push他的左右孩子了
不然会死循环
#include <iostream>
#include <string>
#include <cstdio>
#include <stack>
using namespace std;
struct Node
{
char val;
Node* left, *right;
Node(char x):val(x), left(NULL), right(NULL)
{
}
};
string PreSeq, InSeq;
Node* CreateBT(int PreStart, int PreEnd, int InStart, int InEnd)
{
if(PreStart>PreEnd || InStart>InEnd) return NULL;
int InRootPos;
Node* root=new Node(PreSeq[PreStart]);
for(int i=InStart;i<=InEnd; i++)
{
if(InSeq[i]==PreSeq[PreStart])
{
InRootPos=i;
break;
}
}
root->left=CreateBT(PreStart+1, PreStart+InRootPos-InStart, InStart, InRootPos-1);
root->right=CreateBT(PreStart+InRootPos-InStart+1, PreEnd, InRootPos+1, InEnd);
return root;
}
void PostOrder(Node* root)
{
if(root)
{
PostOrder(root->left);
PostOrder(root->right);
cout<<root->val;
}
}
void PostOrder_Iterative(Node* root)
{
if(!root) return ;
Node* p=root,*plast=NULL;
stack<Node* > q;
q.push(p);
while(!q.empty())
{
Node* p=q.top();
if((p->left==NULL && p->right==NULL) || (plast!=NULL && (plast==p->right ||plast==p->left)) )
{
cout<<p->val;
plast=p;
q.pop();
}
else
{
if(p->right)
q.push(p->right);
if(p->left)
q.push(p->left);
}
}
}
int main()
{
freopen("BT.in","r",stdin);
cin>>PreSeq>>InSeq;
Node* root= CreateBT(0,(int)PreSeq.size()-1, 0, (int)InSeq.size()-1);
PostOrder_Iterative(root);
return 0;
}