题意:

根据二叉树中序和后序建立二叉树,从根结点开始计算和到叶子结点,输出总和最小的叶子结点,如果有俩个和一样大,输出叶子结点最小的

AC:80ms

#include
        
         #include
         
          #include 
          
           #include
           
            #include
            
             #include
             
              using namespace std;struct Tree{ int curTotal; Tree() { curTotal = 0; }};void buildTree(const int* in, const int* post, int curTotal, int* minTotal, int tl, int * leaf);int readInt(string str, int * const a){ istringstream in(str); int i; int total = 0; while (in >> i) a[total++] = i; return total;}int main(){ //freopen("d:\\1.txt", "r", stdin); string str1, str2; while (getline(cin, str1)) { getline(cin, str2); int inorder[100000]; int postorder[100000]; int tl = readInt(str1, inorder); readInt(str2, postorder); int min = 0x7FFFFFFF; int leaf = 0x7FFFFFFF; buildTree(inorder, postorder, 0, &min, tl, &leaf); cout << leaf << endl; }}void buildTree(const int* in, const int* post, int curTotal, int* minTotal, int tl, int * leaf){ if (tl == 0) return; int cur = -1; for (int i = 0; i < tl; i++) { if (in[i] == post[tl - 1]) { cur = i; break; } } //左孩子长度cur int left = cur; //right长度 tl-cur-1 int right = tl - cur - 1; curTotal += in[cur]; if (tl == 1) { if (curTotal <= *minTotal) { *minTotal = curTotal; *leaf = in[cur]; } } //left buildTree(in, post, curTotal, minTotal, left, leaf); //right buildTree(in + left + 1, post + left, curTotal, minTotal, right, leaf);}