题意:

思路:

2. 从左/右子树递归寻找最小路径和, 为了确保当路径和相等时, 取最小叶节点, 需要把叶子节点的值也和一起返回.

要点:

题目:

代码:

# include 
    
     # include 
     
      # include 
      
       # include 
       
        # include 
        
         # include 
         
          # include 
          
           # include 
           
            # include 
            
             # include 
             
              using namespace std;// 读入两行，第一行中序，第二行后序遍历，// 要求找到从根节点到叶节点路径和最小的叶节点，若有多个最小和，则输出最小的叶节点class Node {public: Node(int n, Node* left, Node* right): n_(n), left_(left), right_(right){} int n_; Node* left_; Node* right_;};// 找到 n 在 vt[begin, end) 中的下标，若找不到，则返回 end// 为了保证重复节点出现时，找到的下标是靠后的节点，这里从后往前找int getIndex(const vector
              
               & vt, int begin, int end, int n) { for (int i=end-1; i>=begin; i--) { if (vt[i] == n) return i; } return end;}// 根据中序与后序遍历创建树// 中序：左根右// 后序：左右根// 算法：由上可以看到，从后序最后开始遍历，找到“根”，然后在中序中找到“根”，// 其左边就是左子树，右边就是右子树Node* buildTree(const vector
               
                & inOrder, int inBegin, int inEnd, const vector
                
                 & postOrder, int postBegin, int postEnd) { if (inBegin>=inEnd || postBegin>=postEnd) return NULL; // 后序的最后一位就是根节点 int n = postOrder[postEnd-1]; int rootIndex = getIndex(inOrder, inBegin, inEnd, n); int leftLength = rootIndex - inBegin; Node* left = buildTree(inOrder, inBegin, rootIndex, postOrder, postBegin, postBegin + leftLength); Node* right = buildTree(inOrder, rootIndex + 1, inEnd, postOrder, postBegin + leftLength, postEnd - 1); Node* root = new Node(n, left, right); return root;}// 释放树空间void freeTree(Node* root) { if (root == NULL) return; freeTree(root->left_); freeTree(root->right_); delete root;}// 找到从根节点到叶节点路径和最小的叶节点，若有多个最小和，则输出最小的叶节点// 返回值，first 表示当前最小和，second 表示对应叶节点的值pair
                 
                   getLeastLeafNode(Node* root) { if (root->left_ == NULL && root->right_ == NULL) { return make_pair(root->n_, root->n_); } pair
                  
                    least; if (root->left_ == NULL && root->right_ != NULL) { least = getLeastLeafNode(root->right_); } else if (root->left_ != NULL && root->right_ == NULL) { least = getLeastLeafNode(root->left_); } else { pair
                   
                     left = getLeastLeafNode(root->left_); pair
                    
                      right = getLeastLeafNode(root->right_); if (left.first < right.first) { least = left; } else if (left.first > right.first) { least = right; } else { // left.first == right.first least = left.second < right.second ? left : right; } } return make_pair(least.first + root->n_, least.second);}int main(int argc, char const *argv[]){ #ifndef ONLINE_JUDGE freopen("548_i.txt", "r", stdin); freopen("uva_o.txt", "w", stdout); #endif // 输入 string inLine; string postLine; while (getline(cin, inLine) && getline(cin, postLine)) { int n; vector
                     
                       inOrder, postOrder; // 读取一行中的各个 int // 中序 istringstream issIn(inLine); while (issIn >> n) inOrder.push_back(n); // 后序 istringstream issPost(postLine); while (issPost >> n) postOrder.push_back(n); // 建树，分析，输出 Node* root = buildTree(inOrder, 0, inOrder.size(), postOrder, 0, postOrder.size()); cout << getLeastLeafNode(root).second << endl; freeTree(root); } return 0;}
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    

环境: C++ 4.5.3 - GNU C++ Compiler with options: -lm -lcrypt -O2 -pipe -DONLINE_JUDGE

改进: 

参考: