Leetcode/maxPathSum.cpp at main · ChongXern/Leetcode · GitHub

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/** https://leetcode.com/problems/binary-tree-maximum-path-sum/
 * Dynamic Programming, Tree, DFS, Binary Tree
 * Hard
*/

#include <iostream>
using namespace std;

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:
    void dpAugment(TreeNode* root) {
        if (!root) {
            return;
        }
        dpAugment(root->left);
        dpAugment(root->right);
        if (root->left) {
            root->val += root->left->val;
        }
        if (root->right) {
            root->val += root->right->val;
        }
        return;
    }
    void findMax(TreeNode* root, int& currMax) {
        if (root->val > currMax) {
            currMax = root->val;
        }
        if (root->left) {
            findMax(root->left, currMax);
        }
        if (root->right) {
            findMax(root->right, currMax);
        }
        return;
    }
    int maxPathSum(TreeNode* root) {
        dpAugment(root);
        int max = root->val;
        findMax(root, max);
        return max;
    }
};

int main() {
    TreeNode* root = new TreeNode(2);
    root->left = new TreeNode(-1);
    Solution solution;
    int max = solution.maxPathSum(root);
    cout << max << endl; // Should be 2, don't have to travel to the leaf
}