3.4 如何求一棵二叉树的最大子树的和

难度系数：★★★★☆　被考察系数：★★☆☆☆

题目描述：

给定一棵二叉树，它的每个结点都是正整数或负整数，如何找到一棵子树，使得它所有结点的和最大？

分析与解答：

要求一棵二叉树的最大子树和，最容易想到的办法就是针对每棵子树，求出这棵子树中所有结点的和，然后从中找出最大值。恰好二叉树的后序遍历就能做到这一点。在对二叉树进行后序遍历的过程中，如果当前遍历的结点的值与其左右子树和的值相加的结果大于最大值，则更新最大值。如下图所示：

在上面这个图中，首先遍历结点-1，这个子树的最大值为-1，同理，当遍历到结点9时，子树的最大值为 9，当遍历结点 3 的时候，这个结点与其左右孩子结点值的和（3-1+9=11）大于最大值9。因此，此时最大的子树为以3为根结点的子树，以此类推，直到遍历完整棵树为止。实现代码如下：

程序的运行结果为

算法性能分析：

这个算法与二叉树的后序遍历有相同的时间复杂度，即为 O（n），其中，n 为二叉树的结点个数。