This approach uses a recursive depth-first search (DFS) to explore every path in the binary tree. We calculate the maximum path sum that a node can contribute to its parent, which is the largest possible sum of the path from this node to any leaf node passing through this node. We keep updating the global maximum path sum during the recursion.
Time Complexity: O(n), where n is the number of nodes in the binary tree. We traverse each node exactly once.
Space Complexity: O(h), where h is the height of the tree. This space is used by the call stack for recursion.
1#include <limits.h>
2
3struct TreeNode {
4 int val;
5 TreeNode *left;
6 TreeNode *right;
7 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8};
9
10class Solution {
11public:
12 int maxPathSum(TreeNode* root) {
13 int max_sum = INT_MIN;
14 maxGain(root, max_sum);
15 return max_sum;
16 }
17
18 int maxGain(TreeNode* node, int &max_sum) {
19 if (!node) return 0;
20 int left_gain = std::max(maxGain(node->left, max_sum), 0);
21 int right_gain = std::max(maxGain(node->right, max_sum), 0);
22 int price_newpath = node->val + left_gain + right_gain;
23 max_sum = std::max(max_sum, price_newpath);
24 return node->val + std::max(left_gain, right_gain);
25 }
26};The solution uses a similar recursive method named maxGain as in the Python approach. This method computes the maximum gain from children nodes while traversing the tree. For each node, it calculates left_gain and right_gain and updates the max_sum if the sum rooted at the current node is greater. This helps in maintaining the maximum path sum. As compared to the Python approach, error checks like returning early from null nodes are done explicitly.
In this approach, we utilize dynamic programming principles alongside tree traversal to compute the maximum path sum. This method is more about reformulating the tree's recursive structure into a form that allows storing intermediate results to optimize operations across the different subtrees. This method is especially useful for understanding different formulations but often overlaps logically with recursive DFS.
Time Complexity: O(n), covering a single pass over all nodes.
Space Complexity: O(h), necessitated by call stack usage designated by the tree height h.
1class TreeNode {
2 int val;
3 TreeNode left;
4 TreeNode right;
5 TreeNode(int x) { val = x; }
6}
7
8public class Solution {
9 int maxSum = Integer.MIN_VALUE;
10 public int maxPathSum(TreeNode root) {
11 calculateMaxSum(root);
12 return maxSum;
13 }
14 private int calculateMaxSum(TreeNode node) {
15 if (node == null) return 0;
16 int leftGain = Math.max(calculateMaxSum(node.left), 0);
17 int rightGain = Math.max(calculateMaxSum(node.right), 0);
18 int priceNewPath = node.val + leftGain + rightGain;
19 maxSum = Math.max(maxSum, priceNewPath);
20 return node.val + Math.max(leftGain, rightGain);
21 }
22}In this solution, we employ a recursive method calculateMaxSum that computes sub-results by leveraging already seen sub-tree sub-results. By traversing each node once, we update a global max value maxSum with results derived from each node acting as a center of a new path. This method hence avoids recomputation by relying on previously calculated results, drawing dynamic programming parallels.