clueless coding // TODO: be smarter

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;
}