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 1return
[ [5,4,11,2], [5,8,4,5] ]
A: 就是简单的递归调用
public class Solution { public List<List<Integer>> pathSum(TreeNode root, int sum) { List<List<Integer>> list = new LinkedList<List<Integer>>(); if(root == null) return list; if(root.left == null && root.right == null){ if(sum==root.val){ List<Integer> l = new LinkedList<Integer>(); l.add(root.val); list.add(l); } return list; } if(root.right!=null){ List<List<Integer>> rightList = pathSum(root.right,sum-root.val); for(List<Integer> ll:rightList) ll.add(0,root.val); list.addAll(rightList); } if(root.left!=null){ List<List<Integer>> leftList = pathSum(root.left,sum-root.val); for(List<Integer> ll:leftList) ll.add(0,root.val); list.addAll(leftList); } return list; } }
Mistakes:
1: 当到了leaf节点,并且相等的时候,忘了返回, 艹
2: ,当不满足的时候,要返回空,而不是null。
Learned:
1: ArrayList 有个
add(int index,
E element) |
------------------------第二遍-----------------
和第一遍不一样的地方就在于, 重新弄了一个函数, 把all 作为参数传过去了。
public class Solution { public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) { ArrayList<ArrayList<Integer>> all = new ArrayList<ArrayList<Integer>>(); ArrayList<Integer> path = new ArrayList<Integer>(); pathSum(root, sum, path, all); return all; } private void pathSum(TreeNode root, int sum,ArrayList<Integer> path,ArrayList<ArrayList<Integer>> all ){ if(root == null) return; ArrayList<Integer> curPath = new ArrayList<Integer>(path); curPath.add(root.val); if(root.left == null && root.right == null){ if(root.val == sum) all.add(curPath); } if(root.left != null) pathSum(root.left, sum - root.val, curPath, all); if(root.right != null) pathSum(root.right, sum - root.val, curPath, all); } }
No comments:
Post a Comment