题目描述

Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

样例

Example 1:

Input: [1,2,3]

       1
      / \
     2   3

Output: 6
Example 2:

Input: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

Output: 42

算法1

(递归) $O(n)$

helper返回该节点的最大path sum，求出左节点和右节点的path sum，update global maximum

时间复杂度

每个节点都需要遍历，O（n）
递归调用栈，O（n）

参考文献

C++ 代码

class Solution {
public:
    int maxPathSum(TreeNode* root) {
        if(!root) return 0;
        int res=INT_MIN;
        helper(root, res);
        return res;
    }
    int helper(TreeNode* root, int& res)
    {
        if(!root) return 0;
        int left=max(0, helper(root->left, res));
        int right=max(0, helper(root->right, res));
        res=max(res, left+right+root->val);
        return max(left, right)+root->val;
    }
};

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla