2019独角兽企业重金招聘Python工程师标准>>>
剑指offer上的一个题。
这里也有:http://www.lintcode.com/zh-cn/problem/binary-tree-path-sum/, 可以用来测试写的代码的正确性
给定一个二叉树,找出所有路径中各节点相加总和等于给定 目标值
的路径。
一个有效的路径,指的是从根节点到叶节点的路径。
样例
给定一个二叉树,和 目标值 = 5
:
1/ \2 4/ \2 3
返回:
[[1, 2, 2],[1, 4]
]
贴上一个很容易理解的代码:(忘了哪来的。。)
private ArrayList<ArrayList<Integer>> listAll = new ArrayList<ArrayList<Integer>>();
private ArrayList<Integer> list = new ArrayList<Integer>();public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {if(root == null) {return listAll;}list.add(root.val);target -= root.val;if(target == 0 && root.left == null && root.right == null){listAll.add(new ArrayList<Integer>(list));}FindPath(root.left, target);FindPath(root.right, target);list.remove(list.size()-1);return listAll;
}