Given a 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.

For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.

后续遍历, 返回根节点的时候check一个局部最大localMax为结点本身,节点本身加左侧path最大,节点本身加右侧path最大,以及节点加左右path最大之和:

localMax = max(v, v + leftChild, v + rightChild, v + leftChild + rightChild)

globalMax = max(globalMax, localMax)

但是这个localMax不可以返回,因为如果取了左右两个path得到最大,则该path已经封闭无法传给上层结点。所以回传的局部最大仅为: max(v, v + leftChild, v + rightChild)

以此遍历全部节点得到整体最大


class Solution {
public:
        int maxSum;
    
        int recursiveFindMaxSum(TreeNode* node)
        {
                if(node)
                {
                        int lval = 0;
                        if(node->;left) lval = recursiveFindMaxSum(node->;left);
                        int rval = 0;
                        if(node->right) rval = recursiveFindMaxSum(node->right);
            
                        if(lval < 0) lval = 0;
                        if(rval < 0) rval = 0;
            
                        int localMax = max(node->val, node-&amp;gt;val + lval + rval);
                        maxSum = max(maxSum, localMax);
            
                        localMax = max(node->val, max(node->val + lval, node->val + rval));
                        return localMax;
                }
        }
    
        int maxPathSum(TreeNode* root) 
        {
                maxSum = 0x80000000;
                if(root)
                {
                        recursiveFindMaxSum(root);
                }
                return maxSum;
        }
};
O(n), 26ms

Leave a Reply

Your email address will not be published. Required fields are marked *