输入一棵二叉树和一个整数,打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
示例: 给定如下二叉树,以及目标和 sum = 22
,
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
返回:
[ [5,4,11,2], [5,8,4,5] ]
提示:
节点总数 <= 10000
实际上就是先序遍历,记录路径,回退的时候记得remove掉叶子
解法1 :7ms 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 class Solution { List<List<Integer>> result = new ArrayList<>(); int sum; public List<List<Integer>> pathSum(TreeNode root, int sum) { this .sum = sum; lookSum(root, new ArrayList<>()); return result; } public void lookSum (TreeNode root,List<Integer> integerList) { if (root == null ){ return ; } ArrayList<Integer> integerArrayList = new ArrayList<>(integerList); integerArrayList.add(root.val); if (root.left == null && root.right == null ){ if (integerArrayList.stream().mapToInt(Integer::intValue).sum() == sum) { result.add(integerArrayList); } return ; } lookSum(root.left, integerArrayList); lookSum(root.right, integerArrayList); } }
执行用时:7 ms 内存消耗:42.2 MB
缺点:
每次都new了
每次都计算了数组了和了
stream 是要慢一点
优化 :3ms 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution { List<List<Integer>> result = new ArrayList<>(); int sum; public List<List<Integer>> pathSum(TreeNode root, int sum) { this .sum = sum; lookSum(root, new ArrayList<>(),0 ); return result; } public void lookSum (TreeNode root,List<Integer> integerList,int cur_sum) { if (root == null ){ return ; } ArrayList<Integer> integerArrayList = new ArrayList<>(integerList); integerArrayList.add(root.val); if (root.left == null && root.right == null ){ if (cur_sum+root.val == sum) { result.add(integerArrayList); } return ; } lookSum(root.left, integerArrayList,cur_sum+root.val); lookSum(root.right, integerArrayList, cur_sum + root.val); } }
执行用时:3 ms 内存消耗:42.9 MB 缺点
不用每次都计算和了,把和标记下
每次都new有点不划算
优化 :1ms 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 class Solution { List<List<Integer>> result = new ArrayList<>(); int sum; public List<List<Integer>> pathSum(TreeNode root, int sum) { this .sum = sum; lookSum(root, new ArrayList<>(),0 ); return result; } public void lookSum (TreeNode root,List<Integer> integerList,int cur_sum) { if (root == null ){ return ; } integerList.add(root.val); if (root.left == null && root.right == null ){ if (cur_sum+root.val == sum) { result.add(new ArrayList<>(integerList)); } integerList.remove(integerList.size() - 1 ); return ; } lookSum(root.left, integerList,cur_sum+root.val); lookSum(root.right, integerList, cur_sum + root.val); integerList.remove(integerList.size() - 1 ); } }
执行用时:1 ms 内存消耗:39.7 MB