LeetCode/Binary Tree Maximum Path Sum.cpp at master · windshg/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
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

// straight-forward solution
class Solution {
public:
    int maxPathSum(TreeNode *root) {
        int ret = 0, sps = 0;
        maxPathSumRec(root, sps, ret);
        return ret;
    }

    void maxPathSumRec(TreeNode *root, int &singlePathSum, int &maxSum) {
        if (!root) return;
        singlePathSum = root->val;
        maxSum = root->val;
        int lsps = 0, lms = INT_MIN, rsps = 0, rms = INT_MIN;
        maxPathSumRec(root->left, lsps, lms);
        maxPathSumRec(root->right, rsps, rms);
        singlePathSum = max(singlePathSum, singlePathSum + max(lsps, rsps));
        maxSum = max(maxSum, lms);
        maxSum = max(maxSum, rms);
        maxSum = max(maxSum, singlePathSum);
        maxSum = max(maxSum, lsps + rsps + root->val);
    }
};

// shorter code
class Solution {
public:
    int maxPathSum(TreeNode *root) {
        int ret = INT_MIN;
        maxPathSumRec(root, ret);
        return ret;
    }

    int maxPathSumRec(TreeNode *root, int &ret) {
        if (!root) return 0;
        int l = maxPathSumRec(root->left, ret);
        int r = maxPathSumRec(root->right, ret);
        int ps = max(root->val, max(l, r) + root->val);
        ret = max(ret, ps);
        ret = max(ret, l + r + root->val);
        return ps;
    }
};