鸿 网 互 联 www.68idc.cn

u012734829的专栏

来源:互联网 作者:佚名 时间:2014-12-30 21:27
Given a binary tree and a sum, find all root-to-leaf paths where each paths sum equals the given sum.For example:Given the below binary tree andsum =

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example:
Given the below binary tree and sum = 22, 5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1

return

[ [5,4,11,2], [5,8,4,5] ] 要写出路径和满足要求的所有路径 典型的回溯法递归求解 代码如下: public class Solution { public List<List<Integer>> pathSum(TreeNode root, int sum) { List<List<Integer>> res=new ArrayList<List<Integer>>(0); List<Integer> tmp=new ArrayList<Integer>(); pathsearch(res, tmp, sum, 0, root); return res; } public void pathsearch(List<List<Integer>> res,List<Integer> tmp,int sum,int cur,TreeNode root){ if(root==null)return; List<Integer> ntmp=new ArrayList<Integer>(); ntmp.addAll(tmp); ntmp.add(root.val); if(root.left==null&&root.right==null){ if(sum==cur+root.val){ res.add(ntmp); } return; } if(root.left!=null){ pathsearch(res, ntmp, sum, cur+root.val, root.left); } if(root.right!=null){ pathsearch(res, ntmp, sum, cur+root.val, root.right); } } }

网友评论
<