Crack LeetCode 之 124. Binary Tree Maximum Path Sum

本文主要是介绍Crack LeetCode 之 124. Binary Tree Maximum Path Sum，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://leetcode.com/problems/binary-tree-maximum-path-sum/

本题的难点在于每条路径可以由树中的任意两个节点相连组成，解题方法还是递归。需要注意的是递归函数的返回值不是子树的和，而是包含根节点的左子树、根节点或者包含根节点的右子树，这也是本题的递归函数和其他题目不同的地方。本题的时间复杂度是O(n)，空间复杂度也是O(n)。以下是C++代码和python代码。
 

class Solution {
public:int maxPathSum(TreeNode * root) {if (root == NULL)return 0;int res = root->val;helper(root, res);return res;}int helper(TreeNode * root, int & res){if (root == NULL)return 0;int left = helper(root->left, res);int right = helper(root->right, res);int cur = root->val + (left>0 ? left : 0) + (right>0 ? right : 0);if (cur>res)res = cur;return root->val + max(left, max(right, 0));}
};

class Solution:maxVal = 0def maxPathSum(self, root):if root == None:return 0maxVal = root.valself.helper(root)return maxValdef helper(self):if root == None:return 0left = helper(root.left);right = helper(root.right);cur = root.val + max(left, 0) + max(right, 0)if cur > maxVal:maxVal = curreturn root.val + max(left, max(right,0))

 

这篇关于Crack LeetCode 之 124. Binary Tree Maximum Path Sum的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---