バイナリ検索ツリー - 最も重いパスアルゴリズムを取得する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>&を引数として変更する必要があります（効果的に2つの値を返す必要があるため、参照型の場合は&に注意してください）。

空のベクターで呼び出します。

あなたはnode->left上の再帰呼び出しを行う行する前に、あなたはインスタンスのよう元のベクトル、std::vector<int> vec_left(input_vector)とstd::vector<int> vec_right(input_vector)を保存する必要があります。次に、2つのコピーを再帰呼び出しに渡します。

コードでは、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;  
}