二叉树前序、中序、后序非递归遍历和指针建树、二叉搜索树转链表、序

最近又有面试，懒得复习代码了，干脆把代码翻到简书上，偶尔看看

问题：

• 1、给二叉树中序和前序，指针建树
• 2、给后序和中序，指针建树
• 3、非递归打印前序、中序、后序
• 4、之子型打印、层次遍历
• 5、对称
• 6、二叉搜索树转指针 递归、非递归
• 7、序列化、反序列化
• 8、某一路径和的二叉树， 求和树

输入数据input.txt

4 5 2 6 7 3 1
4 2 5 1 6 3 7

#include <bits/stdc++.h>
using namespace std;
struct TreeNode{
    int val;
    TreeNode* parent;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x):val(x),left(nullptr),right(nullptr),parent(nullptr){};
};

TreeNode *PostIncreate(vector<int> post, vector<int> in){
    if(post.empty()) return nullptr;
    TreeNode* root;
    vector<int>::iterator index=find(in.begin(),in.end(),post.back());
    int left=index-in.begin();
    int right=in.end()-index-1;
    vector<int> post1(post.begin(),post.begin()+left);
    vector<int> post2(post.begin()+left,post.end()-1);
    vector<int> in1(in.begin(),index);
    vector<int> in2(index+1,in.end());
    root=new TreeNode(*index);
    root->left=PostIncreate(post1,in1);
    root->right=PostIncreate(post2,in2);
    return root;
}

void bfs(TreeNode* root) {
    if(!root)
        return;
    queue<TreeNode *> q;
    q.push(root);

    while(!q.empty()) {
        TreeNode *p = q.front();
        q.pop();
        if (p->left)
            q.push(p->left);
        if (p->right)
            q.push(p->right);
        cout << p->val << " ";
    }
    cout << endl;
}

void pre_display(TreeNode* root) {
    stack<TreeNode *> s;
    s.push(root);
    while(!s.empty()) {
        TreeNode *p = s.top();
        s.pop();
        cout << p->val << " ";
        if(p->right) {
            s.push(p->right);
        }
        if(p->left) {
            s.push(p->left);
        }
    }
    cout << " end of pre" << endl;
}

void PostIterS(TreeNode *p){
    stack<TreeNode*> s;
    setParent(p);
    string result;
    if(p) s.push(p); 
    while(!s.empty()){
        if(s.top()!=p->parent){
            while(TreeNode* temp=s.top()){
                if(temp->left){
                    if(temp->right){
                        s.push(temp->right);
                    }
                    s.push(temp->left);
                }
                else{
                s.push(temp->right);
                }
            }
            s.pop();
        }
    p=s.top();
    s.pop();
    printf("%d",p->val);
    }
}

TreeNode *Convert(TreeNode *pHead)
{
    if (!pHead)
        return nullptr;
    TreeNode *last = nullptr;
    stack<TreeNode *> s;
    TreeNode *p = pHead;
    while (p || !s.empty())
    {
        if (p)
        {
            s.push(p);
            p = p->left;
        }
        else
        {
            p = s.top();
            s.pop();
            p->left = last;
            if (last)
            {
                last->right = p;
            }
            last = p;
            p = p->right;
        }
    }
    while (last->left)
    {
        last = last->left;
    }
    return last;
}

void in_display(TreeNode* root) {
    stack<TreeNode *> s;
    TreeNode *p = root;
    while (!s.empty() || p) {
        if(p) {
            s.push(p);
            p = p->left;
        }
        else {
            p = s.top();
            s.pop();
            cout << p->val << " ";
                p = p->right;
        }
    }
    cout << endl;
}



int get_height(TreeNode * root) {
    if(!root)
        return 0;
    queue<TreeNode *> q;
    q.push(root);
    int next = 1;
    int cnt = 0;
    int result = 0;
    while (!q.empty()){
        TreeNode*  p =q.front();
        q.pop();
        --next;
        if(p->left) {
            q.push(p->left);
            ++cnt;
        }
        if(p->right) {
            q.push(p->right);
            ++cnt;
        }
        if(next == 0) {
            next = cnt;
            cnt = 0;
            ++result;
        }
    }
    return result;
}
void Convert(TreeNode* p,TreeNode*&pre){
    if(!p) return;
    if(p->left)
    Convert(p->left,pre);
    p->left=pre;
    if(pre){
        pre->right=p;
    }
    pre=p;
    if(p->right){
        Convert(p->right,pre);
    }

}
TreeNode* ConvertR(TreeNode* pHead){
    if(!pHead) return nullptr;
    TreeNode* pre=nullptr;
    Convert(pHead,pre);
    while(pre->left)
        pre=pre->left;
    return pre;
}
    // void Mirror(TreeNode *pRoot) {
    //     if(!pRoot)  return;
    //     TreeNode *p=pRoot;
    //     queue<TreeNode*> q;
    //     q.push(p);
    //     while(!q.empty()){
    //         p=q.front();q.pop();
    //         if(p->left) {q.push(p->left);}
    //         if(p->right){q.push(p->right);}
    //         TreeNode *temp=p->left;
    //         p->left=p->right;
    //         p->right=temp;
    //     }
    void Mirror(TreeNode *pRoot){
        if(!pRoot) return ;
        queue<TreeNode*> q;
        q.push(pRoot);
        while(!q.empty()){
            TreeNode* p=q.front();q.pop();
            if(p->left){q.push(p->left);}
            if(p->right){q.push(p->right);}
            TreeNode* temp=p->left;
            p->left=p->right;
            p->right=temp;
        }
    }

    bool isSame(TreeNode*p1,TreeNode*p2){
        if(!p1&&!p2) return true;
        if((!p1&&p2)||(!p2&&p1)) return false;
        if(p1->val==p2->val){
            return isSame(p1->left,p2->left)&&isSame(p1->right,p2->right);
        }
        else{
            return false;
        }
    }


    // }
    // void bfs(TreeNode* p){
    //     if(!p) return;
    //     queue<TreeNode*> q;
    //     q.push(p);
    //     while(!q.empty()){
    //         p=q.front();q.pop();
    //         printf("%d ",p->val);
    //         if(p->left) q.push(p->left);
    //         if(p->right) q.push(p->right);
    //     }
    // }

        vector<int> PrintFromTopToBottom(TreeNode* root) {
            vector<int> res;
            if(!root) return res;
            queue<TreeNode* > q;
            q.push(root);
            while(!q.empty()){
                TreeNode *p=q.front();q.pop();
                res.push_back(p->val);
                if(p->left) q.push(p->left);
                if(p->right) q.push(p->right);
            }
            return res;
    }
    void disp(vector<int> v){
        for(auto x:v){
            printf("%d",x);
        }
    }
    // void bfs(TreeNode *p){
    //     if(!p) return ;
    //     queue<TreeNode *> q;
    //     q.push(p);
    //     while(!q.empty()){
    //         p=q.front();
    //         q.pop();
    //         printf("%d",p->val);
    //         if(p->left) q.push(p->left);
    //         if(p->right) q.push(p->right);
    //         if(q.empty()) printf("\n");
    //         else printf(" ");
    //     }
    // }
   void bfsLevel(TreeNode* p){
        if(!p) return ;
        queue<TreeNode*> q;
        q.push(p);
        int prt=1;
        int nextLevel=0;
        while(!q.empty()){
            p=q.front(); q.pop();
            printf("%d",p->val);
            prt--;
            if(p->left) {
                q.push(p->left);
                nextLevel++;
            }
            if(p->right){
                q.push(p->right);
                nextLevel++;
            }
            if(prt==0) {prt=nextLevel;nextLevel=0; printf("\n");}
        }
    }
    void zPrint(TreeNode*p){
        if(!p) return ;
        stack<TreeNode*> s[2];
        int current=0;
        int nxt=1;
        s[current].push(p);
        //int cnt=0;
        while(!s[0].empty()||!s[1].empty()){
            p=s[current].top();s[current].pop();
            printf("%d ",p->val);
            if(current==0){
                if(p->left) s[nxt].push(p->left);
                if(p->right) s[nxt].push(p->right);
            }
            else if(current==1){
                if(p->right) s[nxt].push(p->right);
                if(p->left) s[nxt].push(p->left);
            }
            if(s[current].empty()){
                printf("\n");
                int temp=current;
                current=nxt;
                nxt=temp;
            }
        }
    }
    vector<vector<int> > Print(TreeNode* pRoot) {
        vector<vector<int> > v;
        if(!pRoot) return v;
        int current=0;
        int nxt=1;
        stack<TreeNode*> s[2];
        s[current].push(pRoot);
        vector<int> row;
        while(!s[0].empty()||!s[1].empty()){
            TreeNode* p=s[current].top();s[current].pop();
            row.push_back(p->val);
            if(current==0){
                if(p->left) s[nxt].push(p->left);
                if(p->right) s[nxt].push(p->right);
            }
            else if(current==1){
                if(p->right) s[nxt].push(p->right);
                if(p->left) s[nxt].push(p->left);
            }
            if(s[current].empty()){
                v.push_back(row);
                row.clear();
                int temp=current;
                current=nxt;
                nxt=temp;
            }
        }
        return v;
    }
    bool isSymm(TreeNode* p1,TreeNode*p2){
        if(!p1&&!p2) return true;
        if((!p1&&p2) ||(!p2&&p1)) return false;
        if(p1->val==p2->val)
        return isSymm(p1->left,p2->right)&&isSymm(p1->right,p2->left);
        else{
        return false;
        }
    }
void searchLeaf(TreeNode* p){
    if(!p) return ;
    stack<TreeNode*> s;
    s.push(p);
    while(!s.empty()){
        p=s.top();s.pop();

        if(p->right) s.push(p->right);
        if(p->left) s.push(p->left);
        if((!p->left)&&(!p->right)){
        printf("%d",p->val);
        if(!s.empty()) printf(" ");
        else printf("\n");
        }
    }

}
    void disp(vector<vector<int> > &v){
        for(auto x:v){
            for(auto y:x){
                printf("%d ",y);
            }
            printf("\n");
        }
    }
    TreeNode* Deserialize(string &str) {
        TreeNode* root=nullptr;
        if(str.size()==0) return nullptr;
        string::iterator deli=str.begin()+str.find_first_of(',');
        
        string num(str.begin(),deli);
        str.erase(str.begin(),deli+1);
        int val=0;
        if(num!="#"){
        val=stoi(num);
        root=new TreeNode(val);
        }
        else return root;
        root->left=Deserialize(str);
        root->right=Deserialize(str);
        return root;
    }
    string Serialize(TreeNode *root) {    
        string node;
        if(!root) {return "#,";}
        if(root) {node+=to_string(root->val);node+=",";}
        node+=Serialize(root->left);
        node+=Serialize(root->right);
        return node;
    }

    void FindPath(TreeNode* root, int expectNumber,int current,vector<int> &path, vector<vector<int> > &v){
        current+=root->val;
        path.push_back(root->val);
        bool isLeaf=(!root->left)&&(!root->right);
        if(isLeaf&&(current==expectNumber)){
            v.push_back(path);
        }

        if(root->left)
        FindPath(root->left,expectNumber,current,path,v);
        if(root->right)
        FindPath(root->right,expectNumber,current,path,v);
        path.pop_back();
    }
    vector<vector<int> > FindPath(TreeNode *root, int expectNumber){
        vector<  vector<int> > v;
        if(!root) return v;
        vector<int> path;
        int current=0;
        FindPath(root,expectNumber,current,path,v);
        return v;
    }

    void sumTree(TreeNode *p,int &sum,int val){
         val=p->val;
         bool isLeaf=(!p->left)&&(!p->right);
         if(isLeaf){
             sum+=val;
             p->val=0;
         }
         if(p->left)
         sumTree(p->left,sum,val);
         if(p->right)
         sumTree(p->right,sum,val);
         
    }

int main(){
    ios::sync_with_stdio(false);
    freopen("input.txt","r",stdin);
    string str;
    int num=0;
    while(getline(cin,str)){
        vector<int> post;
        vector<int> in;
        stringstream s1(str);
        while(s1>>num){
            post.push_back(num);
        }
        getline(cin,str);
        stringstream s2(str);
        while(s2>>num){
            in.push_back(num);
        }
        TreeNode* root=PostIncreate(post,in);
        TreeNode* mirrorRoot=PostIncreate(post,in);
        // vector<int> v=bfs(root);
        // disp(v);
        //zPrint(root);
        // vector<vector<int> > v=Print(root);
        string str=Serialize(root);
        // printf("%s\n",str);
        cout<<str<<endl;
        TreeNode *x=Deserialize(str);
        // bfs(x);
        bfsLevel(x);
        // cout<<"same?: "<<isSame(root,root)<<endl;
        // Mirror(root);
        // bfs(root);
        // cout<<"same?: "<<isSame(root,mirrorRoot)<<endl;

        // cout<<"isSymm?: "<<isSymm(root,mirrorRoot)<<endl;
        

    }
}