#### clueless coding// TODO: be smarter

Cracking the Coding Interview Elements of Programming Interviews Programming Interviews Exposed # LeetCode 124. Binary Tree Maximum Path Sum: C++ Solution

## Problem Statement

Given a binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

``````Function Signature (C++):
int maxPathSum(TreeNode* root)

Inputs:
1
/ \
2   3

Outputs:
6

We can go from 2->1->3, or we can go from 3->1->2.

Inputs:
1
/ \
2   3
/ \
1   2
Outputs:
8

We can go from 2->1->3->2.
``````

## TL;DR Code Solution

``````int maxToRoot(TreeNode *root, int &re) {
if (!root) return 0;
int l = maxToRoot(root->left, re);
int r = maxToRoot(root->right, re);
if (l < 0) l = 0;
if (r < 0) r = 0;
if (l + r + root->val > re) re = l + r + root->val;
return root->val += max(l, r);
}

int maxPathSum(TreeNode *root) {
int max = -2147483648;
maxToRoot(root, max);
return max;
}
``````