请问leetcode 126 <Binary Tree Maximum Path Sum>

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 does not need to go through the root.

这里面的path对结束节点有要求么？看了一下path的定义，似乎一定是要叶子节点。但是题目又没有强调……所以请问，tree里面的任何节点都可以作为结束节点还是必须是叶子？

感谢感谢

定义中没有规定必须叶子作为路径的起始点，这是因为节点的值可以是负数，所以未必路径越长总和就越大，这一点很重要。换句话说，如果假设总和最大路径已经找到，那么起始点一定要么是叶子要么被负节点堵住。 这道题是典型的递归解法。注意到任何一条路径都有一个最小祖先作为“转折点”，然后问题就转化成从转折点向下寻找两个单向的最路径。这样就可以用递归解决。

zzgzzm 发表于 2016-9-7 22:36
定义中没有规定必须叶子作为路径的起始点，这是因为节点的值可以是负数，所以未必路径越长总和就越大，这一 ...

太感谢了。因为编了一下，发现会从一棵树的左边一只加到右边来选择path，不知这个对不对。

用post-order traversal的顺序计算以每个节点作为最小祖先的最大路径。先从叶子开始，因为以叶子为转折点的最大路径就是本身。当左右两个叶子计算之后就可以计算其父节点为转折点的最大路径=node->val + max(0, node->left->val+Lmax) + max(0, node->right->val+Rmax). 其中Lmax是从left child （不含本身）向下的单向最大路径，这个一定是在之前递归时已经计算过的了。然后同时保持对以每个节点作为转折点的最大路径取最大值。
当 node->left->val+Lmax  < 0时，说明left child value是负数，并且再向下延伸再多也无法补偿成正数，所以求最大路径是一定要用max(0,*)来确保这种情况干脆不向left child延伸。