如何在树

Question

实现Kadane算法（最大Subarry）下面是本文给出了这个问题：binary tree maximum path sum

给定一个二叉树，找到最大路径总和。

对于这个问题，路径被定义为从某个>起始节点到沿着父子连接的树中的任何节点的任何节点序列。 >路径必须至少包含一个节点，并且不需要经过根目录。

例如：

 -5 
    / \ 
    1  4 
    /\ /\ 
    -6 5 11 -2 
/\  /\ 
9 10  7 -1 
      /\ 
       18 7 

这应该给答案11 + 4 +（-2）+（-1）+ 18，我想用一个O(n)算法得到这个答案。

我该如何得到它？我GOOGLE了它，但什么也没找到。 注意：给定的树是一个不平衡的二叉树。

Answer 1

在这种特殊情况下，您可以使用简单的DFS来计算O(n)中所需的值。

注意树中的任何路径都有一个深度最小的节点。所以，你可以为每一个节点：

• 在这个节点
• 在这个节点结束

你可以计算这些值的最佳路径的子树出发迄今为止看到的最好路径对于使用来自子节点的值的父节点。

要更新在当前节点结束的最佳路径采取的最大：

• 最佳路径在左节点+节点值整理
• 最佳路径在右节点+节点值
• 节点值整理

要更新迄今为止看到的最好的路径采用的最大值：

• 迄今所看到的左侧子最佳路径
迄今所看到的右子
• 最佳路径
• 最佳路径在当前节点完成
• 最佳路径在左节点+节点值+最佳路径在右节点
整理整理

下面是一个示例实现：

#include <algorithm> 
#include <limits> 

using namespace std; 
void getMax(TreeNode* n, double& maxInTree, double& maxUpToNode) { 
    if(!n) 
    { 
     maxInTree = - numeric_limits<double>::infinity(); 
     maxUpToNode = - numeric_limits<double>::infinity(); 
     return; 
    } 
    double leftMaxInTree; 
    double leftMaxUpToNode; 
    getMax(n->left, leftMaxInTree, leftMaxUpToNode); 

    double rightMaxInTree; 
    double rightMaxUpToNode; 
    getMax(n->right, rightMaxInTree, rightMaxUpToNode); 

    maxInTree = max(leftMaxInTree, rightMaxInTree); 
    maxInTree = max(maxInTree, leftMaxUpToNode + n->val + rightMaxUpToNode); 
    maxUpToNode = max(leftMaxUpToNode + n->val, n->val + rightMaxUpToNode); 
    maxUpToNode = max<double>(maxUpToNode, n->val); 
    maxInTree = max(maxInTree, maxUpToNode); 
} 

int maxPathSum(TreeNode* root) { 
    double maxInTree; 
    double maxUpToNode; 
    getMax(root, maxInTree, maxUpToNode); 
    return maxInTree; 
} 

可以此话我为了减少COMPLE使用double代码的xity。事实上，我在整个解决方案中有一个if（而整数，我将不得不根据子节点的存在/不存在来分离许多不同的情况）