Share my thoughts here. Similar with Maximum Subarray


  • 1

    This problem is very similar with #58 Maximum Subarray. But after turn it into a binary tree from an array, it becomes not so obvious. For the Maximum Subarray, we will have two variables to trace max value and current value. For this problem, it should also be like this, otherwise, we don't know where the start point is. Whenever you stand on a node, you want to look left subtree and right subtree. After by whatever method you get the maxValue of left subtree and maxValue of right subtree, you have the following choices:

    1. add left subtree maxValue, and right subtree maxValue and the current node value up. See if it could be larger then maximum value.
    2. Only chose one subtree, either left subtree or right subtree. And it and current node value. Before return the value, you should check if it is larger than 0. Because if it's less than 0, no reason you want to return it.

    So here is code.

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

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.