时间戳

首页 > 解决方案 > 树的路径中的最大总和是多少

c++ - 树的路径中的最大总和是多少

问题描述

https://practice.geeksforgeeks.org/problems/maximum-path-sum/1 这是来自极客的问题。我写了我的答案。但这是错误的。我的逻辑有什么问题？ 

int path(Node *root, int & max_sum)
{
  if(root==NULL)
    return 0;
  int l=path(root->left,max_sum);
  int r=path(root->right,max_sum);
  max_sum=max(max_sum,l+r+root->data);
  return max(l,r)+root->data;
}

int maxPathSum(Node *root) 
{
  int max_sum=INT_MIN;
  path(root,max_sum);
  return max_sum;
  // code here
}

标签： c++algorithm

解决方案

问题陈述说

找到从一个叶节点到另一个叶节点的最大可能总和。

所以，当你这样做

 max_sum=max(max_sum,l+r+root->data);

您将需要检查是否root有两个孩子。否则，它们将不会被考虑在最终答案中。

你也做过

if(root==NULL)  return 0;

和

max(l,r)+root->data;

这两个组合都覆盖了一个值为负的叶子节点子节点，因为 0 大于任何负整数。

所以总的来说你的代码应该是这样的：

int path(Node *root, int & max_sum)
{
  if(root==NULL) return 0;
  int l=path(root->left,max_sum);
  int r=path(root->right,max_sum);
  if(root->left != NULL && root->right != NULL){
      max_sum = max(max_sum,l + r + root->data);
  }

  if(root->left != NULL && root->right == NULL) return  l + root->data;
  if(root->right != NULL && root->left == NULL) return  r + root->data;
  return max(l,r) + root->data;
}

int maxPathSum(Node *root) 
{
  int max_sum=INT_MIN;
  path(root,max_sum);
  return max_sum;
}

推荐阅读