一起刷leetcode(124): 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.
已邀请:

jefflee

赞同来自: Dream_whui


这个题关键是没说是不是每个结点的数值为正,所以可能是负的。
自己的思路:递归,每个子问题保留两个结果:p1= 最大路径长, p2= 结束于根节点的最大路径(我称为立即最大路径 immediate max path)长度。
拿到一个根节点后,对它的左右子树递归调用求解过程,左边的两个最大路径记为lp1和lp2, 右边记为rp1和rp2.
那么根节点的 p2=max(val, lp2+val, rp2+val). p1=max(lp1, rp1, p2, lp2+rp2+val). 这里有点tricky的是,p1的一个候选是lp2+rp2+val,即左右子树的最大立即路径都和根节点连,但是这样一个路径显然不能作为上一级的立即最大路径的一部分了,因为那样再连到上一级的根节点,就有了个分叉,不是path了。
    class Solution {
    public:
        struct maxPath{
            int maxPathLen;
            int maxImmPathLen;
            maxPath(): maxPathLen(-10000000), maxImmPathLen(-10000000) {}
        };
    
        maxPath _maxPathSum(TreeNode *root) {
            maxPath leftMaxPath, rightMaxPath;
            maxPath currMaxPath;
            if(root->left)
                leftMaxPath = _maxPathSum(root->left);
            if(root->right)
                rightMaxPath = _maxPathSum(root->right);
            
            int maxImmPath = std::max(leftMaxPath.maxImmPathLen, rightMaxPath.maxImmPathLen);
            int children_root_len = maxImmPath + root->val;
            currMaxPath.maxImmPathLen = std::max(children_root_len, root->val);
            int maxChildrenLen = std::max(leftMaxPath.maxPathLen, rightMaxPath.maxPathLen);
            currMaxPath.maxPathLen = std::max(maxChildrenLen, currMaxPath.maxImmPathLen);
            int bothChildrenLen = leftMaxPath.maxImmPathLen + root->val + rightMaxPath.maxImmPathLen;
            if( currMaxPath.maxPathLen < bothChildrenLen )
                currMaxPath.maxPathLen = bothChildrenLen;
            return currMaxPath;
        }
        
        int maxPathSum(TreeNode *root) {
            maxPath max = _maxPathSum(root);
            return max.maxPathLen;
        }
    };

要回复问题请先登录注册