7°

输入一颗二叉树的跟节点和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。

//方案一:

public class Solution {

ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();

ArrayList<Integer> temp = new ArrayList<Integer>();

public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {

if(root==null)
    return list;
f(root,target,0);
return list;

}

public void f(TreeNode root, int target,int sum){ if(root==null) return;

sum=root.val + sum;

if(root.left==null&amp;&amp;root.right==null){
    if(sum==target)
    {
        temp.add(root.val);
        ArrayList&lt;Integer&gt; temp1 = new ArrayList&lt;Integer&gt;(temp);
        list.add(temp1);
        temp.remove(temp.size()-1);
    }
  return;
}

temp.add(root.val);
f(root.left,target,sum);
f(root.right,target,sum);
temp.remove(temp.size()-1);

}

}

//方案二:

public class Solution {

ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();

ArrayList<Integer> temp = new ArrayList<Integer>();

public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) { if(root==null) return list; f(root,target,0); return list; }

public void f(TreeNode root, int target,int sum){ if(root==null) return;

sum=root.val + sum;

if(sum==target){
    if(root.left==null&amp;&amp;root.right==null)
    {
        temp.add(root.val);
        ArrayList&lt;Integer&gt; temp1 = new ArrayList&lt;Integer&gt;(temp);
        list.add(temp1);
        temp.remove(temp.size()-1);
    }
  return;
}
//可以从这个地方优化
else if(sum&gt;target)
    return;
    
temp.add(root.val);
//也可以从这个地方优化
if(root.left!=null&amp;&amp;((sum+root.left.val)&lt;=target))
f(root.left,target,sum);
if(root.right!=null&amp;&amp;((sum+root.right.val)&lt;=target))
f(root.right,target,sum);
temp.remove(temp.size()-1);

}

}

方案二为方案一的优化:去掉不必要的递归

本文由【南】发布于开源中国,原文链接:https://my.oschina.net/u/2511906/blog/3136632

全部评论: 0

    我有话说: