LeetCode 124. 二叉树中的最大路径和（DFS）

示例 1:

输入: [1,2,3]

       1
      / \
     2   3

输出: 6
示例 2:

输入: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

输出: 42

/**
 * 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 {	//C++
public:
    int maxPathSum(TreeNode* root) {
        int maxanswer = INT_MIN;
        maxsum(root, maxanswer);
        return maxanswer;
    }
    int maxsum(TreeNode* root, int &maxanswer) 
    {
    	if(root == NULL)
    		return 0;
    	int left = maxsum(root->left,maxanswer);
    	int right = maxsum(root->right,maxanswer);
    	int curmax = root->val;
    	if(left > 0)
        	curmax += left;
        if(right > 0)
        	curmax += right;
        if(curmax > maxanswer)
    		maxanswer = curmax;
    	return max(root->val,max(left+root->val,right+root->val));
    }
};

class Solution:# py3
    def maxPathSum(self, root: TreeNode) -> int:
        self.maxsum = float('-inf')
        def dfs(root):
            if not root:
                return 0
            l = dfs(root.left)
            r = dfs(root.right)
            v = root.val
            curmax = v
            if l>0:
                curmax += l
            if r>0:
                curmax += r
            self.maxsum = max(curmax, self.maxsum)
            return max(v, max(v+l, v+r))
        dfs(root)
        return self.maxsum