[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.

Tags: tree, depth-first-search

10/10/2015 udpate

divide-and-conquer approach

o(n) solution, use a fancy recursion function, do two works together.

It returns the path sum starts from root node to nodes below,

res is the current maximum sum path

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int MININT = 0x8fffffff;
    int maxPathSum(TreeNode* root) {
        int res = MININT;
        pathSum(root, res);
        return res;
    }
    //return the max path sum that starts from root
    //res is the maximum path sum in this tree
    int pathSum(TreeNode * root, int& res){
        if(root == nullptr) return -1;
        int left = pathSum(root->left, res);
        int right = pathSum(root->right, res);
        int tmp = root->val;
        tmp = left > 0? tmp + left: tmp;
        tmp = right > 0? tmp + right: tmp;
        res = max(res, tmp);
        return max(max(left, right), 0) + root->val;
    }
};

 

O(nlogn) solution, not quite efficient, time limit excced.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int MININT = 0x80000000;
    int maxPathSum(TreeNode* root) {
        if(root == nullptr){
            return MININT;
        }
        int left = maxPathSum(root->left);
        int right = maxPathSum(root->right);
        int leftPath = maxToRootSum(root->left);
        int rightPath = maxToRootSum(root->right);
        int tmp = root->val;
        tmp = leftPath > 0? tmp + leftPath: tmp;
        tmp = rightPath > 0? tmp + rightPath: tmp;
        return max(left, max(right, tmp));
    }
    int maxToRootSum(TreeNode * root){
        if(root == nullptr) return -1;
        int left = maxToRootSum(root->left);
        int right = maxToRootSum(root->right);
        int tmp = root->val;
        tmp = max(left, right) > 0? tmp + max(left, right): tmp;
        return tmp;
    }
};

 

 

 

Tag里没写divide-and-conquer. 但我还是先想到了一个分治的算法.

这道题让我想起数据结构书上,第一章的那个作为引子的,最大子序列问题.我想着把这个树近似成一个多叉数组来处理,这里化用了原书里的第三个分而治之的算法,时间复杂度O(nlogn).但是竟然没让我过!说是超时.我还在想O(n)的算法.或许应该化用书中第四个算法.记得那个算法是O(n)的复杂度.

版本一:O(nlogn),分治算法,超时

需要注意,max只接受两两参数的比较.如果多参数比较的话,需要嵌套max函数.

C++:

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
/**
 * divide and conque
 **/
 
    int maxPathSum(TreeNode *root) {
        int leftSum, rightSum, leftAdjacentSum, rightAdjacentSum;
        bool isLeftSet = false;
        bool isRightSet = false;
        //leaf node
        if(root->left == NULL && root->right == NULL){
            return root->val;
        }
        
        else{
            if(root->left != NULL){
                isLeftSet = true;
                leftSum = maxPathSum(root->left);
                leftAdjacentSum = maxAdjacentPathSum(root->left);
            }
            if(root->right != NULL){
                isRightSet = true;
                rightSum = maxPathSum(root->right);
                rightAdjacentSum = maxAdjacentPathSum(root->right);
            }
            //due to the if condition in line 21, either isLeftSet or isRightSet should be true.
            if(isRightSet == false){
                //isLeftSet is true
                return max(leftSum, max(leftAdjacentSum, 0) + root->val);
            }
            else if(isLeftSet == false){
                //isRightSet is true
                return max(rightSum, max(rightAdjacentSum, 0) + root->val);
            }
            else{
                //both isRightSet and isLeftSet is true
                //if either the rightAjacentSum or the leftAjacentSum is smaller than 0, discard it.
                return max(max(leftSum, rightSum), max(leftAdjacentSum, 0) + max(rightAdjacentSum, 0) + root->val);    
            }
            
        }
    }
    
    int maxAdjacentPathSum(TreeNode *root){
        int maxLeft, maxRight;
        bool isLeftSet = false;
        bool isRightSet = true;
        if(root->left == NULL && root->right == NULL){
            return root->val;
        }
        if(root->left != NULL){
            maxLeft = maxAdjacentPathSum(root->left);
            isLeftSet = true;
        }
        if(root->right != NULL){
            maxRight = maxAdjacentPathSum(root->right);
            isRightSet = true;
        }
        
        if(isRightSet == false){
            return max(maxLeft, 0) + root->val;    
        }
        else if(isLeftSet == false){
            return max(maxRight, 0) + root->val;
        }
        else{
            return max(max(maxRight, maxLeft), 0) + root->val;
        }
    }
};

一月二十二号晚更新:

找到了时间复杂度为O(n)的办法。其实版本一已经很接近O(n)了,只是我的递归没有写好,maxAdjacentPathSum是多余的,它的工作完全可以合并在maxPathSum里。从结构上也不难发现,它的函数结构和maxPathSum有惊人的相似。

实际上,maxAdjacentSum所需要的信息在maxPathSum的递归时已经得到了。正如数据结构书的第一章介绍递归时所讲,“永远不要把同一个东西计算两次。”

我只是机械性地把两个函数合并在了一起。虽然AC了,但执行效率依旧比第一名有一些差距。不知有没有更有效率的方法?或者用循环来代替递归?

版本二:简化后的分治算法,AC

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class ReturnValue{
public:
    int maxPathSum;
    int maxAdjacentSum;
    ReturnValue(int x, int y):maxPathSum(x), maxAdjacentSum(y){}
};
class Solution {
public:
/**
 * divide and conquer
 **/
    int maxPathSum(TreeNode *root){
        return _maxPathSum(root)->maxPathSum;
    }
    
    ReturnValue * _maxPathSum(TreeNode *root) {
        int leftSum, rightSum, leftAdjacentSum, rightAdjacentSum;
        bool isLeftSet = false;
        bool isRightSet = false;
        ReturnValue * p;
        //leaf node
        if(root->left == NULL && root->right == NULL){
            return new ReturnValue(root->val, root->val);
        }
        
        else{
            if(root->left != NULL){
                isLeftSet = true;
                p = _maxPathSum(root->left);
                leftSum = p->maxPathSum;
                leftAdjacentSum = p->maxAdjacentSum;
            }
            if(root->right != NULL){
                isRightSet = true;
                p = _maxPathSum(root->right);
                rightSum = p->maxPathSum;
                rightAdjacentSum = p->maxAdjacentSum;
            }
            //due to the if condition in line 21, either isLeftSet or isRightSet should be true.
            if(isRightSet == false){
                //isLeftSet is true
                int thisMaxPathSum = max(leftSum, max(leftAdjacentSum, 0) + root->val);
                int thisMaxAdjacentSum = max(leftAdjacentSum, 0) + root->val;
                return new ReturnValue(thisMaxPathSum, thisMaxAdjacentSum);
                
            }
            else if(isLeftSet == false){
                //isRightSet is true
                int thisMaxPathSum = max(rightSum, max(rightAdjacentSum, 0) + root->val);
                int thisMaxAdjacentSum = max(rightAdjacentSum, 0) + root->val;
                return new ReturnValue(thisMaxPathSum, thisMaxAdjacentSum);
                
            }
            else{
                //both isRightSet and isLeftSet is true
                //if either the rightAjacentSum or the leftAjacentSum is smaller than 0, discard it.
                int thisMaxPathSum =  max(max(leftSum, rightSum), max(leftAdjacentSum, 0) + max(rightAdjacentSum, 0) + root->val);  
                int thisMaxAdjacentSum = max(max(rightAdjacentSum, leftAdjacentSum), 0) + root->val;
                return new ReturnValue(thisMaxPathSum, thisMaxAdjacentSum);
            }
            
        }
    }
};

Selection_006

 

Leave a comment

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.