Leetcode 124. Binary Tree Maximum Path Sum

题目解法：recursion

题目

解法：recursion

参考leetcode官方解法：https://leetcode.com/problems/binary-tree-maximum-path-sum/solution/ 关键点在于两个，一个是用全局的变量来保存最大值，另一个点在于如何计算以某个节点为根节点所能得到的路径最大值。left_gain和right_gain得到的方式也很需要思考 python代码：

class Solution: def maxPathSum(self, root: TreeNode) -> int: def max_gain(node): nonlocal max_val if not node: return 0 left_gain = max(max_gain(node.left),0) right_gain = max(max_gain(node.right),0) new_max = node.val+left_gain+right_gain max_val = max(new_max,max_val) return node.val+max(left_gain,right_gain) max_val = float('-inf') max_gain(root) return max_val

C++代码：

class Solution { int max_val = -INT_MAX; public: int maxPathSum(TreeNode* root) { helper(root); return max_val; } int helper(TreeNode* node){ if (!node) return 0; int left_gain = max(helper(node->left),0); int right_gain = max(helper(node->right),0); int new_max = node->val + left_gain + right_gain; max_val = max(max_val,new_max); return node->val + max(left_gain,right_gain); } };