Given a binary tree, find the maximum path sum from any two alive nodes within the tree. We can assume a node is an alive node if and only if it is a leaf node, indicated by an asterisk below.
What if the tree we are given can have alive nodes at non-leaf nodes as well? Find the maximum path between any two alive nodes within the tree. A maximum path may only have the two alive nodes without any other alive nodes in between. For example, the alive nodes are highlighted with asterisks.
Example:
5
/ \
2* 0
/ \ / \
100* 50* 4* 15*Return the maximum path sum between two alive nodes.
This is a tree DP / DFS problem about finding the maximum path sum whose two endpoints are alive nodes, while no other alive nodes may appear on the path. The standard approach is to do a postorder traversal and compute the best downward contribution from each node, then combine left and right contributions to update a global answer when the current node can serve as a valid join point. The main challenge is enforcing the constraint that only the two endpoints are alive nodes, so the state must distinguish ordinary nodes from alive nodes and prevent paths from passing through additional alive nodes. Careful handling of negative values and one-sided paths is important.
