分治法避免定义多个递归函数,应该使用ResultType

总结:对二叉树应用分治法时,应避免定义多个递归函数,当出现需要递归求解多种的结果时,尽量使用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。

上一篇:让虚拟机的软盘盘符不显示(适用于所有windows系统包括Windows Server)


下一篇:VIM使用(一) VIM插件管理利器-vundle