路径总和 II
给你二叉树的根节点 root 和一个整数目标和 targetSum ,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
1 2
| 输入:root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 输出:[[5,4,11,2],[5,8,4,5]]
|
思路:求root节点开始到叶子节点和为target的路径,等于当前节点加上子节点到叶子节点和为:target - root.val的路径。采用先序遍历,在遍历过程维护当前路径与子路径并及时回退
代码:
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 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
|
class Solution { List<List<Integer>> result = new ArrayList(); public List<List<Integer>> pathSum(TreeNode root, int targetSum) { if(root == null) { return result; } List<Integer> tmp = new ArrayList(); findPath(root, targetSum, tmp); return result; }
public void findPath(TreeNode node, int target, List<Integer> tmp){ int val = node.val; tmp.add(val); target -= val; if(node.left == null && node.right == null) { if(target == 0) { List<Integer> t = new ArrayList(); t.addAll(tmp); result.add(t); } } else{ if(node.left != null) { findPath(node.left, target, tmp); } if(node.right != null) { findPath(node.right, target, tmp); } } tmp.remove(tmp.size()-1); } }
|