Fork me on GitHub

Binary Tree Maximum Path Sum

Posted on

Description

https://leetcode.com/problems/binary-tree-maximum-path-sum/description/

Solution

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxPathSum(TreeNode* root) {
        int max = -10000;
        this->findPath(root, max);
        return max;
    }
    
    int findPath(TreeNode* root, int& max) {
        if (root == NULL) return -100000;
        int left = this->findPath(root->left, max);
        if (left > max) max = left;
        int right = this->findPath(root->right, max);
        if (right > max) max = right;
        int cur = root->val + (left >= 0 ? left : 0) + (right >= 0 ? right : 0);
        if (cur > max) max = cur;
        
        int bias = 0;
        if (left > 0) bias = left;
        if (right > 0  && right > left) bias = right;
        return root->val + bias;
    }
};