中序和后序确定二叉树以及二叉树的递归遍历

红太狼 2022-05-05 09:44 175阅读 0赞

树：Uva548

![70][]

\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_[https://blog.csdn.net/yexiaohhjk/article/details/50519453][https_blog.csdn.net_yexiaohhjk_article_details_50519453]

样例输入：

3 2 1 4 5 7 6

3 1 2 5 6 7 4

7 8 11 3 5 16 12 18

8 3 11 716 18 12 5

255

样例输出

255

1、给定中序和后序（或先序），都能唯一确定一个二叉树。

> node\* creat\_tree(int m1,int n1,int m2,int n2)  
> \{      
>     if (m1>n1) return NULL;//m==n时，建立叶子节点  
>     int tmp=PostOrder\[n2\];  
>     int i=find(InOrder.begin(),InOrder.end(),tmp)-InOrder.begin();  
>     cout<<tmp<<" "<<i;   //system("pause");  
>     int cnt=i-m1;//表示共有多少左子树  
>     node \*u=new node;  
>     u->v=tmp;  
>     u->left=creat\_tree(m1,i-1,m2,m2+cnt-1);  
>     u->right=creat\_tree(i+1,n1,m2+cnt,n2-1);  
>     return u;  
> \}

2、深度递归遍历二叉树

> void dfs(node \*u,int sum)  
> \{  
>     sum+=u->v;  
>     if(!u->left&&!u->right)  
>         if(sum<best\_sum||(sum==best\_sum&&u->v<isum))  
>         \{  
>             best\_sum=sum;  
>             isum=u->v;  
>         \}  
>     if(u->left) dfs(u->left,sum);  
>     if(u->right) dfs(u->right,sum);  
> \}

3、释放动态生成的空间

> void remove\_tree(node \*u)  
> \{  
>     if(u==NULL) return;  
>     remove\_tree(u->left);  
>     remove\_tree(u->right);  
>     delete u;  
> \}
> 
>

整体代码：

#include<iostream>
    #include<climits>
    #include<vector>
    #include<algorithm> 
    using namespace std;
    
    struct node
    {
    	int v;
    	node *left;
    	node *right;
    	node():v(0),left(NULL),right(NULL){}
    };
    
    node *root;
    int best_sum=INT_MAX;//最小的和
    int isum=INT_MAX;// 最小和时的下标 
    int a1[]={7,8,11,3,5,16,12,18};
    int a2[]={8,3,11,7,16,18,12,5};
    vector<int> InOrder(a1,a1+sizeof(a1)/sizeof(int));
    vector<int> PostOrder(a2,a2+sizeof(a2)/sizeof(int));
    
    /*
    node* creat_tree(int m,int n)
    {	
    	if (m>n) return NULL;//m==n时，建立叶子节点 
    	int tmp=PostOrder[n];
    	int i=find(InOrder.begin(),InOrder.end(),tmp)-InOrder.begin();
    	cout<<tmp<<" "<<i;system("pause");
    	node *u=new node;
    	u->v=tmp;
    	u->left=creat_tree(m,i-1);
    	u->right=creat_tree(i+1,n);
    	return u;
    }
    */
    
    
    node* creat_tree(int m1,int n1,int m2,int n2)
    {	
    	if (m1>n1) return NULL;//m==n时，建立叶子节点 
    	int tmp=PostOrder[n2];
    	int i=find(InOrder.begin(),InOrder.end(),tmp)-InOrder.begin();
    	cout<<tmp<<" "<<i;   //system("pause");
    	int cnt=i-m1;//表示共有多少左子树 
    	node *u=new node;
    	u->v=tmp;
    	u->left=creat_tree(m1,i-1,m2,m2+cnt-1);
    	u->right=creat_tree(i+1,n1,m2+cnt,n2-1);
    	return u;
    }
    
    void dfs(node *u,int sum)
    {
    	sum+=u->v;
    	if(!u->left&&!u->right)
    		if(sum<best_sum||(sum==best_sum&&u->v<isum))
    		{
    			best_sum=sum;
    			isum=u->v;
    		}
    	if(u->left) dfs(u->left,sum);
    	if(u->right) dfs(u->right,sum);
    } 
    
    void remove_tree(node *u)
    {
    	if(u==NULL) return;
    	remove_tree(u->left);
    	remove_tree(u->right);
    	delete u;
    }
    
    int main()
    {
    	root=creat_tree(0,InOrder.size()-1,0,PostOrder.size()-1);
    	dfs(root,0);
    	cout<<isum<<endl;
    }

[70]: /images/20220505/3a4ff3326678426cb8dd81d09c5d1146.png
[https_blog.csdn.net_yexiaohhjk_article_details_50519453]: https://blog.csdn.net/yexiaohhjk/article/details/50519453