Binary Tree Maximum Path Sum
Hard · Trees · about 30 minutes
Asked at Meta, Google, Amazon, Microsoft.
A path in a binary tree is any chain of nodes where consecutive nodes are parent and child; it can start and end anywhere and doesn't have to touch the root, but it can't visit a node twice. For a non-empty tree, find the path whose node values add up to the largest total and return that total.