Tree UVA - 548 (DFS+建立二叉树)-蒲公英云

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

男娘i 2022-02-28 13:22 302阅读 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;
}