Tree UVA - 548 (DFS+建立二叉树)

男娘i 2022-02-28 13:22 179阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsZXgxOTk3MjIy_size_16_color_FFFFFF_t_70][]

解题思路:

根据中序后序建立二叉树,利用DFS便利每条路径的和

这里要注意输入:

bool read_List(int* a){
    	string line; 
    	if(!getline(cin,line)) return false;  //如果为空,则直接退出
    	stringstream ss(line);  //化为stream流
    	int x;
    	n = 0;
    	while(ss >> x) a[n++] = x;
    	return n > 0;
    }

我们可以在读入字符串后,利用stringstream去除空格,把字符串中的数字全部读出来

#include <iostream>
    #include <algorithm>
    #include <vector>
    #include <queue>
    #include <string>
    #include <sstream>
    using namespace std;
    const int MAXN = 10010;
    int midArr[MAXN],postArr[MAXN];  
    int n;
    int leastNode = 0x3fffffff;
    int minRoute = 0x3fffffff;
    vector<int> routes;
    bool flag = true;
    bool read_List(int* a){
    	string line; 
    	if(!getline(cin,line)) return false;  //如果为空,则直接退出
    	stringstream ss(line);  //化为stream流
    	int x;
    	n = 0;
    	while(ss >> x) a[n++] = x;
    	return n > 0;
    }
    struct stNode{
    	int stData;
    	stNode *lchild,*rchild;
    	stNode(int _value){
    		stData = _value;
    		lchild = rchild = nullptr;
    	}
    };
    //DFSfind
    void DFSfind(stNode* sroot){
    	if(sroot->lchild == nullptr && sroot->rchild == nullptr){
    		routes.push_back(sroot->stData);
    		//求和
    		int tempSum = 0;
    		for(int k = 0; k < routes.size();++k){
    			tempSum += routes[k];  //加上tempSum的和
    		}
    		if(tempSum == minRoute){
    		   if(sroot->stData < leastNode){
    			   leastNode = sroot->stData;
    		   }
    		}
    		else if(tempSum < minRoute){
    			minRoute = tempSum;
    			leastNode = sroot->stData;
    		}
    		routes.pop_back();
    	}
    	if(sroot->lchild != nullptr){
    		routes.push_back(sroot->stData);
    		DFSfind(sroot->lchild);
    		routes.pop_back();  //出队
    	}
    	if(sroot->rchild != nullptr){
    		routes.push_back(sroot->stData);
    		DFSfind(sroot->rchild);
    		routes.pop_back();
    	}
    }
    
    stNode* buildTree(int posL,int posR,int inL,int inR){
    	if(posL > posR) return nullptr;  
    	int curposRoot = postArr[posR];
    	int curInroot = -1;
    	int k;
    	for(int i = inL;i <= inR;++i){
    	    if(midArr[i] == curposRoot){
    			curInroot = midArr[i];
    			k = i;
    			break;
    		}
    	}
    	if(curInroot == -1) return nullptr;
    	stNode* croot = new stNode(curposRoot);  
    	int numK = k - inL;
    	
    	croot->lchild = buildTree(posL,posL+numK-1,inL,k-1);  //向左
    	croot->rchild = buildTree(posL+numK,posR-1,k+1,inR);  //向右
    	return croot;  //返回头结点
    }
    
    int main(){
    	while(read_List(midArr)){
    		read_List(postArr);
    		leastNode = 0x3fffffff;
            minRoute = 0x3fffffff;
    		routes.clear();
    		stNode* troot = buildTree(0,n-1,0,n-1);  //建树
    		DFSfind(troot);
    		cout<<leastNode<<endl;
    	}
    
    	system("PAUSE");
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsZXgxOTk3MjIy_size_16_color_FFFFFF_t_70]: /images/20220228/7eb5704f4baf4b15b2e480f775d50f5e.png