Open jason89521 opened 3 months ago
Link: https://leetcode.com/problems/binary-tree-maximum-path-sum/description/
Use post-order traversal to calculate the maximum path sum.
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int maxPathSum(TreeNode* root) { int maxVal = 0; bool hasInit = false; traversal(root, maxVal, hasInit); return maxVal; } int traversal(TreeNode* root, int& maxVal, bool& hasInit) { if (root == nullptr) { return 0; } auto left = traversal(root->left, maxVal, hasInit); if (left < 0) { left = 0; } auto right = traversal(root->right, maxVal, hasInit); if (right < 0) { right = 0; } auto maxPath = (std::max(left, right) + root->val); if (!hasInit) { hasInit = true; maxVal = maxPath; } else { maxVal = std::max(maxVal, left + right + root->val); } return maxPath; } };
Time complexity:
Practice Dates
Description
Link: https://leetcode.com/problems/binary-tree-maximum-path-sum/description/
Solution
Use post-order traversal to calculate the maximum path sum.
Performance
Time complexity: