二叉搜索树 - 得到最重的路径算法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;  
}