codekofi
← All questions

Binary Tree Maximum Path Sum

HardTrees

The problem

A path is any sequence of nodes where each consecutive pair is joined by an edge, and no node repeats. It may start and end anywhere, and need not touch the root.

Return the largest sum of values along any path. Values may be negative.

maxPathSum({-10, 9, 20, nullopt, nullopt, 15, 7})

One of these three is correct

Two lines apart, at the closest.

The wrong ones are this same code with between two and five lines changed. Some of those changes do not compile. There is no Run button: running all three would turn this into a vote rather than a reading.

1struct Node {
2 int val;
3 Node* left;
4 Node* right;
5};
6
7Node* build(const vector<optional<int>>& level) {
8
9 if (level.empty() || !level[0]) {
10 return nullptr;
11 }
12
13 Node* root = new Node{*level[0], nullptr, nullptr};
14
15 queue<Node*> q;
16
17 int i = 1;
18 int n = level.size();
19
20 while (!q.empty() && i < n) {
21
22 Node* node = q.front();
23
24 if (level[i]) {
25 node->left = new Node{*level[i], nullptr, nullptr};
26 q.push(node->left);
27 }
28
29 i++;
30
31 if (i < n && level[i]) {
32 node->right = new Node{*level[i], nullptr, nullptr};
33 q.push(node->right);
34 }
35
36 i++;
37 }
38
39 return root;
40}
41
42int gain(Node* node, int& best) {
43
44 if (!node) {
45 return 0;
46 }
47
48 int left = max(gain(node->left, best), 0);
49 int right = max(gain(node->right, best), 0);
50
51 int through = node->val + left + right;
52 best = max(best, through);
53
54 return node->val + max(left, right);
55}
56
57int maxPathSum(const vector<optional<int>>& level) {
58
59 Node* root = build(level);
60 int ans = INT_MIN;
61
62 gain(root, ans);
63
64 if (ans == INT_MIN) {
65 return 0;
66 }
67
68 return ans;
69}
1struct Node {
2 int val;
3 Node* left;
4 Node* right;
5};
6
7Node* build(const vector<optional<int>>& level) {
8
9 if (level.empty() || !level[0]) {
10 return nullptr;
11 }
12
13 Node* root = new Node{*level[0], nullptr, nullptr};
14
15 queue<Node*> q;
16
17 int i = 1;
18 int n = level.size();
19
20 while (!q.empty() && i < n) {
21
22 Node* node = q.front();
23 q.pop();
24
25 if (level[i - 1]) {
26 node->left = new Node{*level[i], nullptr, nullptr};
27 q.push(node->left);
28 }
29
30 i++;
31
32 if (i < n && level[i]) {
33 node->right = new Node{*level[i], nullptr, nullptr};
34 q.push(node->right);
35 }
36
37 i++;
38 }
39
40 return root;
41}
42
43int gain(Node* node, int& best) {
44
45 if (!node) {
46 return 0;
47 }
48
49 int left = max(gain(node->left, best), 0);
50 int right = max(gain(node->right, best), 0);
51
52 int through = node->val + left + right;
53 best = max(best, through);
54
55 return node->val + max(left, right);
56}
57
58int maxPathSum(const vector<optional<int>>& level) {
59
60 Node* root = build(level);
61 int ans = INT_MIN;
62
63 gain(root, ans);
64
65 if (ans == INT_MIN) {
66 return 0;
67 }
68
69 return ans;
70}
1struct Node {
2 int val;
3 Node* left;
4 Node* right;
5};
6
7Node* build(const vector<optional<int>>& level) {
8
9 if (level.empty() || !level[0]) {
10 return nullptr;
11 }
12
13 Node* root = new Node{*level[0], nullptr, nullptr};
14
15 queue<Node*> q;
16 q.push(root);
17
18 int i = 1;
19 int n = level.size();
20
21 while (!q.empty() && i < n) {
22
23 Node* node = q.front();
24 q.pop();
25
26 if (level[i]) {
27 node->left = new Node{*level[i], nullptr, nullptr};
28 q.push(node->left);
29 }
30
31 i++;
32
33 if (i < n && level[i]) {
34 node->right = new Node{*level[i], nullptr, nullptr};
35 q.push(node->right);
36 }
37
38 i++;
39 }
40
41 return root;
42}
43
44int gain(Node* node, int& best) {
45
46 if (!node) {
47 return 0;
48 }
49
50 int left = max(gain(node->left, best), 0);
51 int right = max(gain(node->right, best), 0);
52
53 int through = node->val + left + right;
54 best = max(best, through);
55
56 return node->val + max(left, right);
57}
58
59int maxPathSum(const vector<optional<int>>& level) {
60
61 Node* root = build(level);
62 int ans = INT_MIN;
63
64 gain(root, ans);
65
66 if (ans == INT_MIN) {
67 return 0;
68 }
69
70 return ans;
71}