548 - Tree （UVA）

题目链接如下：

Online Judge

开始的代码如下：

#include 
#include 
#include 
#include 
#include 
const int INF = 99999999;
// #define debug
 
std::vector<int> inorder, postorder;
std::string line;
int t, root, minn, key, sum;
std::map<int, int> inloc, left, right;
 
int findRoot(int inLeft, int inRight, int postLeft, int postRight){
    if (inLeft == inRight){
        return 0;
    }
    int rt = postorder[postRight - 1];
    int loc = inloc[rt];
    left[rt] = findRoot(inLeft, loc, postLeft, loc - inLeft + postLeft);
    right[rt] = findRoot(loc + 1, inRight, loc - inLeft + postLeft, postRight - 1);
    return rt;
}
 
void dfs(int k){
    sum += k;
    if (!left[k] && !right[k]){
        if (sum < minn){
            minn = sum;
            key = k;
        } else if (sum == minn && key > k){
            key = k;
        }
        sum -= k;
        return;
    }
    if (left[k]){
        dfs(left[k]);
    }
    if (right[k]){
        dfs(right[k]);
    }
    sum -= k;
}
 
int main(){
    #ifdef debug
    freopen("0.txt", "r", stdin);
    freopen("1.txt", "w", stdout);
    #endif
    while (getline(std::cin, line)){
        std::stringstream in(line);
        while (in >> t){
            inloc[t] = inorder.size();
            inorder.push_back(t);
        }
        getline(std::cin, line);
        std::stringstream post(line);
        while (post >> t){
            postorder.push_back(t);
        }
        root = findRoot(0, inorder.size(), 0, inorder.size());
        minn = INF;
        sum = 0;
        dfs(root);
        printf("%d\n", key);
        inorder.clear();
        postorder.clear();
        left.clear();
        right.clear();
        inloc.clear();
    }
    #ifdef debug
    fclose(stdin);
    fclose(stdout);
    #endif
    return 0;
}

后来看别人的代码发现dfs可以省掉，修改后如下：

#include 
#include 
#include 
#include 
#include 
const int INF = 99999999;
// #define debug
 
std::vector<int> inorder, postorder;
std::string line;
int t, root, minn, key;
std::map<int, int> inloc, left, right;
 
int findRoot(int inLeft, int inRight, int postLeft, int postRight, int tot){
    if (inLeft == inRight){
        return 0;
    }
    int rt = postorder[postRight - 1];
    int sum = tot + rt;
    int loc = inloc[rt];
    left[rt] = findRoot(inLeft, loc, postLeft, loc - inLeft + postLeft, sum);
    right[rt] = findRoot(loc + 1, inRight, loc - inLeft + postLeft, postRight - 1, sum);
    if (!left[rt] && !right[rt]){
        if (sum < minn || (sum == minn && rt < key)){
            minn = sum;
            key = rt;
        }
    }
    return rt;
}
 
int main(){
    #ifdef debug
    freopen("0.txt", "r", stdin);
    freopen("1.txt", "w", stdout);
    #endif
    while (getline(std::cin, line)){
        std::stringstream in(line);
        while (in >> t){
            inloc[t] = inorder.size();
            inorder.push_back(t);
        }
        getline(std::cin, line);
        std::stringstream post(line);
        while (post >> t){
            postorder.push_back(t);
        }
        minn = INF;
        root = findRoot(0, inorder.size(), 0, inorder.size(), 0);
        printf("%d\n", key);
        inorder.clear();
        postorder.clear();
        left.clear();
        right.clear();
        inloc.clear();
    }
    #ifdef debug
    fclose(stdin);
    fclose(stdout);
    #endif
    return 0;
}