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.
这道题本质上是二叉树上的“受限最大路径和”问题：只允许路径的两端是 alive node（题目里用星号标记），中间不能再经过其他 alive node。经典做法是用 DFS 自底向上遍历，每个节点返回“从该节点往下走、连接到某个 alive 叶子 / 活节点的最大贡献值”，同时在遍历过程中维护全局答案，尝试用当前节点作为路径拐点，把左右子树中来自两个不同 alive 节点的最优贡献拼接起来。关键点在于区分普通节点和 alive 节点，避免路径中间再次经过活节点；如果题目允许活节点出现在非叶子位置，那么状态转移时要严格限制路径结构，通常需要记录是否已经碰到活节点。整体是树形 DP / DFS 题，注意处理负值、单侧分支以及只有一个可达 alive 节点的情况。
