二叉搜索樹 - 得到最重的路徑算法C++

Question

使用二叉搜索樹我需要向樹中最重的路徑添加所有int元素。 例如我有20,7,6,9,11,21 應該添加到向量的值將是20,7,9,11 我已經寫了計算最重的路徑的實現，但我不知道如何去改變它，因此正確的元素將被添加到載體：

int Tree::maxBranch(Node* node){ 
    if(node==NULL) 
     return 0; 
    int leftSum=node->data+maxBranch(node->left); 
    int rightSum=node->data+maxBranch(node->right); 
    if(rightSum>leftSum){ 
     return rightSum; 
    } 
    return leftSum;  
} 

Answer 1

書面不保留分行的跟蹤你的代碼，它是緊隨其後 - 它只能得到總和。

您應該更改函數以將std::vector<int>&作爲參數（注意&，對於引用類型，因爲您需要有效地返回兩個值）。

用空的矢量調用它。

，你做node->left遞歸調用行之前，您應該保存原向量，例如，std::vector<int> vec_left(input_vector)和std::vector<int> vec_right(input_vector)。然後將這兩個副本傳遞給遞歸調用。

現在，在代碼中，在return rightSum之前，您應該有一個vec_right.push_back(node->id); input_vector = vec_right;。在之前，您應該也有一個vec_left.push_back(node->id); input_vector = vec_left;。在英語中，你保留了分數最高的分支的路徑，並丟棄另一分支。

Answer 2

快速&髒：

int Tree::maxBranch(Node* node, vector<int>& vec, bool add){ 
    if(node==NULL) 
     return 0; 
    int leftSum=node->data+maxBranch(node->left, vec, false); 
    int rightSum=node->data+maxBranch(node->right, vec, false); 
    if (add) 
     vec.push_back(node->data); 
    if(rightSum>leftSum){ 
     if (add) 
      maxBranch(node->right, vec, true); 
     return rightSum; 
    } 
    if (add) 
     maxBranch(node->left, vec, true); 
    return leftSum;  
}