使用堆栈的二叉树中从根到叶的最大值总和

Question

我正在尝试使用堆栈找到二叉树中从根到叶节点的最大值总和。我写了以下代码，但其中有一个错误。<>

Stacks s;
s.push(root);
maxSum=currSum=0;
      while(!s.isEmpty()) {
        temp = s.top();
        s.pop();
        if( temp->left == null && temp->right == null ) {
          currSum = currSum+temp->data;
          if(currSum > maxSum) {
            maxSum = currSum;
          }
          currSum =0;
        } else {
          currSum = currSum + temp->data;
          if(temp->left) s.push(temp->left);
         if(temp->right) s.push(temp->right);
        }   
      }

我正在尝试做的是计算叶节点的总和并将其分配给maxSum。
例如：- 二叉树是

       1
      /   
    2      3
  /  
4     5

1）我先按 1 然后弹出.当前总和 =1;
2） 按 3 和 2 并弹出 2。cursum = 3 并推送 5 和 4;
3）堆栈现在看起来像4<-5-<3-<1（4是顶部元素）
4）现在由于4是叶节点，我输入if loop并添加currSum = 3 + 4 = 7并弹出4。
5）现在 temp 是 5，我设置 currSum=0，所以当我弹出 5 时 currSum 变成 5 .

任何人都可以帮我修复此错误吗

Answer 1

    10
  /   
 8     2

请考虑为您的代码提供此示例。

1. 第一个 root（10） 被推入堆栈，然后我们立即弹出它。
2. 现在，currsum 变为 10，左 （8） 和右 （2） 节点被推入堆栈。
3. 现在最上面的元素（2） 被弹出并添加到 currsum。现在 currsum 变为 12。
4. 当我们到达叶节点时，maxsum 包含当前值。
5. 并且库尔总和为0。

这是一个错误，因为我们正在失去根值。

6. 现在我们弹出最后一个元素 （8） 并且 currsum 在我们到达叶节点 8.As 具有值，我们与 maxsum（12） 进行比较，最终答案是12 这是错误的。

下面的代码将帮助您完成。尝试使用堆栈代替矢量。

使用命名空间标准;

struct node {
int data;
struct node* left;
struct node* right;
};

struct node* createNode(int k) {
struct node* temp = new node;
temp->left = NULL;
temp->right = NULL;
temp->data = k;

return temp;

}

int tsum(vector<struct node *> path) {
  int sum;
  int n = path.size();
  int i;
  for (i = 0; i < n; i++)
  sum = sum + path[i]->data;
  return sum;
 }
    int maxsum(struct node *root) {
    int currsum = 0, maxsum = 0;
    vector<struct node *> v;    
    v.push_back(root); //Push root
    vector<int> visited(100, 0);
    while (v.size() > 0) {
    visited[v.back()->data] = 1; //whenever node is reached mark visited
    if (v.back()->left != NULL && !visited[v.back()->left->data])
        v.push_back(v.back()->left);
    else if (v.back()->right != NULL && !visited[v.back()->right->data])
        v.push_back(v.back()->right);
    else {
        if (!v.back()->left && !v.back()->right) {
            currsum = tsum(v);
            if (currsum > maxsum)
                maxsum = currsum;
        }
        v.pop_back(); //pop here is used for backtracking
      }
      }
    return maxsum;
    }

int main() {
int sum = 0;
std::vector<int> arr;
/* Constructed binary node is
       1
     /   
    2      3
  /      
 4     5  
 */
struct node *root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
int s = 0;
s = maxsum(root);
cout << "SUM" << s << "n";
return 0;
}