首页 > 数据结构 > 树形结构 > LeetCode-Binary Tree Maximum Path Sum[二叉树]
2014
11-19

LeetCode-Binary Tree Maximum Path Sum[二叉树]

Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.

标签: Tree Depth-first Search
分析

这题很难,路径可以从任意节点开始,到任意节点结束。

可以利用“最大连续子序列和”问题的思路,见第\S \ref{sec:maximum-subarray}节。如果说Array只有一个方向的话,那么Binary Tree其实只是左、右两个方向而已,我们需要比较两个方向上的值。

不过,Array可以从头到尾遍历,那么Binary Tree怎么办呢,我们可以采用Binary Tree最常用的dfs来进行遍历。先算出左右子树的结果L和R,如果L大于0,那么对后续结果是有利的,我们加上L,如果R大于0,对后续结果也是有利的,继续加上R。

代码1

// LeetCode, Binary Tree Maximum Path Sum
// 时间复杂度O(n),空间复杂度O(logn)
class Solution {
public:
    int maxPathSum(TreeNode *root) {
        max_sum = INT_MIN;
        dfs(root);
        return max_sum;
    }
private:
    int max_sum;
    int dfs(const TreeNode *root) {
        if (root == nullptr) return 0;
        int l = dfs(root->left);
        int r = dfs(root->right);
        int sum = root->val;
        if (l > 0) sum += l;
        if (r > 0) sum += r;
        max_sum = max(max_sum, sum);
        return max(r, l) > 0 ? max(r, l) + root->val : root->val;
    }
};

相关题目
Maximum Subarray


  1. bottes vernies blanches

    I appreciate the efforts you men and women place in to share blogs on such sort of matters, it was certainly useful. Keep Posting!

  2. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge

  3. 网站做得很好看,内容也多,全。前段时间在博客园里看到有人说:网页的好坏看字体。觉得微软雅黑的字体很好看,然后现在这个网站也用的这个字体!nice!

  4. 您没有考虑 树的根节点是负数的情况, 若树的根节点是个很大的负数,那么就要考虑过不过另外一边子树了

  5. int half(int *array,int len,int key)
    {
    int l=0,r=len;
    while(l<r)
    {
    int m=(l+r)>>1;
    if(key>array )l=m+1;
    else if(key<array )r=m;
    else return m;
    }
    return -1;
    }
    这种就能避免一些Bug
    l,m,r
    左边是l,m;右边就是m+1,r;