LeetCode题目:Binary Tree Maximum Path Sum

By | 2012 年 12 月 9 日

这道题好难,因为在一颗二叉树中有多种情况,这条最长的路径有可能是从某个中间节点直接到某个叶子节点的,也有可能是两条上述路径连接在一个中间节点上(这个中间节点可能是root也可能不是),也有可能只是一个单独的节点。

情况太多导致问题很复杂,不好分析,这题花了我至少两个小时去解决。

一开始从自上而下的方法去想,想到了可以计算出每一个节点到root的最大值,然后最后拼一下最大值,得到整体最大。但是这里假设了路径都是过root的。显然不对。

然后想level优先遍历的话,如果知道了上面的情况,下面一层可解么?陷入死胡同至少30min,gg。

然后想自下而上,如果知道了左右子树的情况,自身的情况能得到么?很快就有了肯定回答。
但是这个solution也相对复杂,针对每个节点需要知道的是:
1.终止在这个节点上(往自己子树走)的最大路径值是多少
2.经过这个节点的最大值是多少?(从左子树走过自己到右子树)
3.不经过此节点的子树中可能获得的最大值是多少?

在知道这三个量之后,问题变得明确可解了。那就是递归,先计算出左右子树的这三个值,然后:
1.终止在此节点的最大路径,首先是自己的值包含进去,然后如果终止在左或右子树的根节点的最大路径值大于0的话,加上这个值。
2.经过这个节点的最大值,很简单了,左右子树的端点最大值加上自己的值。
3.不经过此节点的最大值,直接查看左右子树中的这个值(如果有左右子树的话),还有左右子树的端点最大值。

这样最后就写出一个递归的算法。如何写成循环还没想好。

2013-1-18,更新了一个更简单的办法.

Question: 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.

代码:

248ms过大集合

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Maxes{
public:
    int tmax;//max of terminated in self
    int pmax;//max of pass self
    int nmax;//max of non-relative to self
    Maxes() {tmax = pmax = 0; nmax = (1 << (sizeof(int) * 8 - 1));}
    inline int getMax() {
        int m = tmax;
        if(m < pmax) m = pmax;
        if(m < nmax) m = nmax;
        return m;
    }
};
class Solution {
public:
    Maxes maxPath(TreeNode *root) {
        Maxes m;
        if(NULL == root)
            return m;

        Maxes l = maxPath(root->left);
        Maxes r = maxPath(root->right);

        //tmax is the max value which terminated at this node
        //when all of it's children is negative, this is it's value
        //or add the max value terminated at it's children
        m.tmax = max(l.tmax,r.tmax);
        if(m.tmax < 0) m.tmax = 0;
        m.tmax += root->val;

        //pmax is the max value which is pass this node
        //that is it's value terminated at it's children (if have, or zero), add self value
        m.pmax = l.tmax + r.tmax + root->val;

        //nmax is the max value which not including current node
        if(root->left)
            m.nmax = l.getMax();
        if(root->right) {
            int rmax = r.getMax();
            if(m.nmax < rmax) m.nmax = rmax;
        }
        return m;
    }
    int maxPathSum(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        Maxes m = maxPath(root);
        int ma = m.getMax();
        return ma;
    }
};

Code rewrite at 2013-1-18, 266ms pass large set, simpler

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    int _curMax;
    //return the max path ending in root
    //and refresh the _curMax with the path sum that go through from left to root to right child.
    int maxWithRoot(TreeNode *root) {
        if(NULL == root) return 0;
        int leftmax = maxWithRoot(root->left);
        int rightmax = maxWithRoot(root->right);

        //the max from left child to right child, accross from root
        int arcmax = root->val;
        if(leftmax > 0) arcmax += leftmax;
        if(rightmax > 0) arcmax += rightmax;
        if(_curMax < arcmax) _curMax = arcmax;

        //the max that end in root
        int pathmax = root->val;
        int submax = std::max(leftmax,rightmax);
        if(submax > 0) pathmax += submax;
        if(_curMax < pathmax) _curMax = pathmax;

        return pathmax;
    }
public:
    int maxPathSum(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        _curMax = INT_MIN;
        maxWithRoot(root);
        return _curMax;
    }
};

5 thoughts on “LeetCode题目:Binary Tree Maximum Path Sum

  1. logicmd

    这题不会做,翻到贵blog,发觉
    Code rewrite at 2013-1-18部分中
    一定有arcmax <= pathmax

    if(_curMax < pathmax) _curMax = pathmax;
    这句可以不要

    Reply

发表评论

电子邮件地址不会被公开。 必填项已用*标注