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

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

谁能帮我解决这个问题

Answer 1

    10
  /   \
 8     2

为您的代码考虑这个示例。

第一个 root(10) 被压入堆栈，我们立即弹出它。
现在 currsum 变为 10，左 (8) 和右 (2) 个节点被压入堆栈。
现在弹出最顶层的元素 (2) 并添加到 currsum.Now 当前总和变为 12。
当我们到达叶节点时，maxsum 包含 currsum 值。
currsum 设为 0。

This is a mistake as we are losing the root value.

现在我们弹出最后一个元素 (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;

}

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

maximum sum of value from root to leaf in a binary tree using stack

binary-tree