Leetcode/124.BinaryTreeMaximumPathSum.h at master · bluepp/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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
/*
    bluepp

    2014-06-01
    2014-07-08
    2014-08-06
    2014-09-14
    2014-11-06

    May the force be with me!

    Problem:    Binary Tree Maximum Path Sum
    Source:     https://oj.leetcode.com/problems/binary-tree-maximum-path-sum/
    Notes:
    Given a binary tree, find the maximum path sum.
    The path may start and end at any node in the tree.
    For example:
    Given the below binary tree,
        1
       / \
      2   3
    Return 6.

    Solution: Recursion...
*/


/* my version, 2014-09-14 */
    int maxPathSum(TreeNode *root) {
        int sum = INT_MIN;
        int curr_sum = 0;

        _path(root, sum, curr_sum);

        return sum;
    }

    void _path(TreeNode *root, int &sum, int &curr_sum)
    {
        if (!root)
        {
            curr_sum = 0;
            return;
        }

        int lsum = 0, rsum = 0;
        _path(root->left, sum, lsum);
        _path(root->right, sum, rsum);

        curr_sum = max(root->val, max(lsum, rsum)+root->val);
        sum = max(sum, max(curr_sum, root->val+lsum+rsum));
    }


--------------------------------------------------------------
   int maxPathSum(TreeNode *root) {
        int maxsum = INT_MIN;

        maxpath(root, maxsum);
        return maxsum;
    }

    int maxpath(TreeNode *root, int &maxsum)
    {
        if (!root) return 0;

        int l = maxpath(root->left, maxsum);
        int r = maxpath(root->right, maxsum);

        int sum = max(root->val, max(l,r) + root->val);
        maxsum = max(maxsum, max(l+r+root->val, sum));

        return sum;

    }