Problem:
Given a binary tree, find the maximum path sum.
For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.
For example:
Given the below binary tree,
|
1 2 3 |
1 / \ 2 3 |
Return 6.
Idea:
Recursion
Time complexity O(n)
Space complexity O(h)
Solution: Recursion
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// Author: Huahua // Runtime: 19 ms class Solution { public: int maxPathSum(TreeNode* root) { if (!root) return 0; int ans = INT_MIN; maxPathSum(root, ans); return ans; } private: int maxPathSum(TreeNode* root, int& ans) { if (!root) return 0; int l = max(0, maxPathSum(root->left, ans)); int r = max(0, maxPathSum(root->right, ans)); int sum = l + r + root->val; ans = max(ans, sum); return max(l, r) + root->val; } }; |
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
""" Author: Huahua Runtime: 138 ms (< 90.38%) """ class Solution(object): def _maxPathSum(self, root): if not root: return -sys.maxint l = max(0, self._maxPathSum(root.left)) r = max(0, self._maxPathSum(root.right)) self.ans = max(self.ans, root.val + l + r) return root.val + max(l, r) def maxPathSum(self, root): self.ans = -sys.maxint self._maxPathSum(root) return self.ans |
Related Problems: