又有leetcode题目来请教了 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

又有leetcode题目来请教了

又有leetcode题目来请教了# JobHunting - 待字闺中

c*r2013-02-26 08:02

1 楼

题目是path sum||
过了小测试。但是没有过大测试。 fail的testcase 是一个堆非常复杂的+/-1 的树。
下面是我的code。麻烦大家来抠一下吧。
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public ArrayList> pathSum(TreeNode root, int sum) {
ArrayList> paths = new ArrayListInteger>>();
pathSum_r(root, sum, new ArrayList(), paths);
return paths;
}
private void pathSum_r(TreeNode root, int sum, ArrayList path,
ArrayList> paths){
if(root == null) return;
if(root.left == null && root.right == null){
if(root.val == sum){
path.add(root.val);
paths.add(path);
}else return;
}else{
if(root.left != null){
ArrayList left_path = new ArrayList();
left_path.addAll(path);
left_path.add(root.val);
pathSum_r(root.left, sum-root.val, left_path, paths);
}
if(root.right != null){
ArrayList right_path = new ArrayList();
right_path.addAll(path);
right_path.add(root.val);
pathSum_r(root.right, sum-root.val, right_path, paths);
}
}
}
}

Y*32013-02-26 08:02

2 楼

我看你的代码逻辑和我的一样，本想改成像C++一样简洁的版本，后发现对java不熟
arraylist和vector还不一样，就放弃了，直接给去了几个没必要的if就过了large
case，八百多毫秒,看来java太慢啊。。。
public class Solution {
public ArrayList> pathSum(TreeNode root, int sum) {
ArrayList> paths = new ArrayListInteger>>();
pathSum_r(root, sum, new ArrayList(), paths);
return paths;
}
private void pathSum_r(TreeNode root, int sum, ArrayList path,
ArrayList> paths){
if(root == null) return;
if(root.val == sum && root.left == null && root.right == null)
{
path.add(root.val);
paths.add(path);
return;
}
ArrayList left_path = new ArrayList();
left_path.addAll(path);
left_path.add(root.val);
pathSum_r(root.left, sum-root.val, left_path, paths);
ArrayList right_path = new ArrayList();
right_path.addAll(path);
right_path.add(root.val);
pathSum_r(root.right, sum-root.val, right_path, paths);
}
}

c*32013-02-26 08:02

3 楼

Java 不慢。back track 就能过large

【在 Y**3 的大作中提到】

: 我看你的代码逻辑和我的一样，本想改成像C++一样简洁的版本，后发现对java不熟
: arraylist和vector还不一样，就放弃了，直接给去了几个没必要的if就过了large
: case，八百多毫秒,看来java太慢啊。。。
: public class Solution {
: public ArrayList> pathSum(TreeNode root, int sum) {
: ArrayList> paths = new ArrayList: Integer>>();
: pathSum_r(root, sum, new ArrayList(), paths);
: return paths;
: }

c*r2013-02-26 08:02

4 楼

多谢多谢了没想到去掉几个if可以有这么大的区别。
leetcode大侠写的judge也很赞！

【在 Y**3 的大作中提到】

c*r2013-02-26 08:02

5 楼

Hi,
我试着把你的code 贴进去了。还是过不了large test啊。

【在 Y**3 的大作中提到】

c*r2013-02-26 08:02

6 楼

Hi,
没明白你说的back track。么有parent link怎样backtrack啊？

【在 c******3 的大作中提到】

: Java 不慢。back track 就能过large

s*c2013-02-26 08:02

7 楼

问题在于recursive call的时候，你每次都重新生成left_path和right_path，然后拷
贝整个path到里面，这样就会慢，不需要这两个额外的arraylist,就用path一个就可，
backtrack就是你走完left child和 right child 之后都回到parent就可，其实就是把
path最后一个element去掉就行。
public class Solution {
public ArrayList> pathSum(TreeNode root, int sum) {
// Start typing your Java solution below
// DO NOT write main() function
ArrayList> results=new ArrayListInteger>>();
ArrayList path=new ArrayList();
pathSumHelper(results,path,root,sum);
return results;

}

public void pathSumHelper(ArrayList>results,
ArrayListpath, TreeNode root, int sum)
{
if(root==null)
return;
if(sum==root.val && root.left==null && root.right==null)
{
//copy nodes to result
path.add(root.val);
ArrayList out=new ArrayList(path);
results.add(out);
}
else
{
path.add(root.val);
pathSumHelper(results,path,root.left,sum-root.val);
pathSumHelper(results,path, root.right, sum-root.val);

}
//resize path, return to the current node's parent
int size=path.size();
if(size>0)
path.remove(size-1);
}
}

Y*32013-02-26 08:02

8 楼

我重复试了几下，有时过(八九百ms)，有时TLE,根本原因就是smartlhc说的，你每递归
一层就生成了额外的ArrayList，我C++的值传递vector也能过。

【在 c*****r 的大作中提到】

: Hi,
: 没明白你说的back track。么有parent link怎样backtrack啊？

c*32013-02-26 08:02

9 楼

Java 用deque也能过large

【在 Y**3 的大作中提到】

:
: 我重复试了几下，有时过(八九百ms)，有时TLE,根本原因就是smartlhc说的，你每递归
: 一层就生成了额外的ArrayList，我C++的值传递vector也能过。