总结：对二叉树应用分治法时，应避免定义多个递归函数，当出现需要递归求解多种的结果时，尽量使用ResultType来让一次递归返回多种结果。
题目：Binary Tree Maximum Path Sum
给出一棵二叉树，寻找一条路径使其路径和最大，路径可以在任一节点中开始和结束（路径和为两个节点之间所在路径上的节点权值之和）。
解法：定义两个函数，maxPathSum(TreeNode root)表示以root为根的树的最大路径长度（即题目所求，至少包含一个节点），rootToAny(TreeNode root)表示从根节点出发的所有路径长度的最大值（至少包含一个节点），则代码如下：
public class Solution {
/**
* @param root: The root of binary tree.
* @return: An integer.
*/
public int maxPathSum(TreeNode root) {
// write your code here
if(root==null)
return Integer.MIN_VALUE;
int pathWithoutRoot = Math.max(maxPathSum(root.left),maxPathSum(root.right));
int pathWithRoot = Math.max(rootToAny(root.left),0)+Math.max(rootToAny(root.right),0)+root.val;
return Math.max(pathWithoutRoot,pathWithRoot);
}
public int rootToAny(TreeNode root){
if(root==null)
return Integer.MIN_VALUE;
return Math.max(0,Math.max(rootToAny(root.left),rootToAny(root.right)))+root.val;
}
}
上面代码在lintcode能提交通过，但在leetcode提交则超时。
我们来分析它的时间复杂度，假设这颗树是一颗平衡二叉树，设maxPathSum函数的时间复杂度为T(n),rootToAny函数时间复杂度是t(n)。则递归式如下：
T(n) = 2T(n/2)+2t(n/2)+C
t(n) = 2t(n/2)+C
解得t(n) = O(n) , T(n) = O(n^2) .
如果我们只定义一个递归函数一次性返回两个值，能将递归式变为
T(n) = 2T(n/2)+C
解得T(n) = O(n).
时间复杂度将会大大降低。
在java中，可通过自己定义一个返回类型来实现返回多个值，代码如下：
public class Solution {
/**
* @param root: The root of binary tree.
* @return: An integer.
*/
private class ResultType {
int singlePath, maxPath;
ResultType(int singlePath, int maxPath) {
this.singlePath = singlePath;
this.maxPath = maxPath;
}
}
private ResultType helper(TreeNode root) {
if (root == null) {
return new ResultType(Integer.MIN_VALUE, Integer.MIN_VALUE);
}
// Divide
ResultType left = helper(root.left);
ResultType right = helper(root.right);
// Conquer
int singlePath =
Math.max(0, Math.max(left.singlePath, right.singlePath)) + root.val;
int maxPath = Math.max(left.maxPath, right.maxPath);
maxPath = Math.max(maxPath,
Math.max(left.singlePath, 0) +
Math.max(right.singlePath, 0) + root.val);
return new ResultType(singlePath, maxPath);
}
public int maxPathSum(TreeNode root) {
ResultType result = helper(root);
return result.maxPath;
}
}
类似的一题为求两个节点的最近公共祖先（LCA），不使用resultType的结果耗时900多ms,使用resultType仅耗时13ms。