Java,给你二叉树的根节点 root 和一个整数目标和 targetSum ,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。 叶子节点 是指没有子节点的节点。
时间: 2024-03-09 09:51:12 浏览: 176
java使用归并删除法删除二叉树中节点的方法
好的,这是一道经典的二叉树遍历问题,我们可以使用深度优先搜索(DFS)来解决。
具体来说,我们可以从根节点开始递归,每次递归时记录当前路径和以及当前路径上的节点,如果当前节点是叶子节点并且路径和等于目标和,就将当前路径加入结果列表中。
Java 代码如下:
```java
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
List<List<Integer>> res = new ArrayList<>();
dfs(root, targetSum, new ArrayList<>(), res);
return res;
}
private void dfs(TreeNode node, int sum, List<Integer> path, List<List<Integer>> res) {
if (node == null) {
return;
}
path.add(node.val);
if (node.left == null && node.right == null && sum == node.val) {
res.add(new ArrayList<>(path));
} else {
dfs(node.left, sum - node.val, path, res);
dfs(node.right, sum - node.val, path, res);
}
path.remove(path.size() - 1);
}
```
其中,dfs 函数的参数分别为当前节点、当前路径和、当前结果路径列表以及最终结果列表。在递归的过程中,我们首先将当前节点加入当前路径中,然后判断当前节点是否为叶子节点并且路径和等于目标和,如果是,则将当前路径加入最终结果列表中,否则继续递归左子树和右子树。最后,将当前节点从当前路径中删除,以便回溯到父节点时能够正确地继续搜索。
阅读全文