共计 976 个字符，预计需要花费 3 分钟才能阅读完成。
题目
给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。
示例: 给定如下二叉树，以及目标和 sum = 22，
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
返回:
[
[5,4,11,2],
[5,8,4,5]
]
题解
这道题目是上一道的延伸，但是需要记录下路径，返回回去。这就是一个典型的 backtrack 的题目了。我们用迭代的方式需要记录中间的路径状态，稍显复杂，所以我们想用递归的方式来解，先探索左子树，然后探索右子树。如果都探索完之后，右满足的就加入到最终结果中。
public class Solution {
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> res = new LinkedList<>();
helper(root, sum, res, new LinkedList<>());
return res;
}
public void helper(TreeNode root, int sum, List<List<Integer>> res, List<Integer> current) {
if (root == null) {
return;
}
current.add(root.val);
if (root.left == null && root.right == null && sum == root.val) {
// leaf node.
res.add(new LinkedList<>(current));
// back track.
current.remove(current.size() – 1);
return;
}
helper(root.left, sum – root.val, res, current);
helper(root.right, sum – root.val, res, current);
// back track.
current.remove(current.size() – 1);
}
}
热门阅读
技术文章汇总
【Leetcode】103. 二叉树的锯齿形层次遍历
【Leetcode】102. 二叉树的层次遍历
【Leetcode】101. 对称二叉树
【Leetcode】100. 相同的树
【Leetcode】98. 验证二叉搜索树
手撕代码 QQ 群：805423079，群密码：1024
