ORIGIN

LeetCode 124. Binary Tree Maximum Path Sum

ACM 1 mins251 words

Problem Description

124. Binary Tree Maximum Path Sum

Analysis

To find the maximum path sum in a binary tree, we can use a recursive approach. The idea is to traverse the tree in a bottom-up manner and calculate the maximum path sum for each node.

We define a helper function maxPathSumHelper(node) that takes a node as input and returns one value:

  1. The maximum path sum starting from the given node, considering only the left or right child paths (if they are positive), or just the node’s value if both children have negative path sums.

Then we calculate the path sum for each node as they are being considered as root node, and compare with the maximum answer.

Finally, we call the helper function maxPathSumHelper(root) on the root of the binary tree to obtain the maximum path sum.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
* 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 maxn = INT_MIN;
int maxPathSum(TreeNode* root) {
maxPathSumHelper(root);
return maxn;
}
int maxPathSumHelper(TreeNode* root) {
if(root == nullptr) return 0;
int left = max(maxPathSumHelper(root->left), 0);
int right = max(maxPathSumHelper(root->right), 0);
maxn = max(maxn, root->val + left + right);
return root->val + max(left, right);
}
};
TOP
COMMENT
  • ABOUT
  • |
o_oyao
  The Jigsaw puzzle is incomplete with even one missing piece. And I want to be the last piece to make the puzzle complete.
Like my post?
Default QR Code
made with ❤️ by o_oyao
©o_oyao 2019-2024

|