二叉树(十六)--二叉树中和为某一值的路径
来源：LeetCode
难度：中等
描述：
输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
示例1：
给定如下二叉树，以及目标和 target = 22
返回：
分析：
本题的要求是，让我们找到所有满足从「根节点」到某个「叶子节点」经过的路径上的节点之和等于目标和的路径。
因此我们需要对树进行遍历，并且在遍历时记录从根节点到当前节点的路径。此处介绍两种解法，具体步骤如下：
解题
方法一：深度优先遍历法
思路：
采用深度优先遍历的方式，枚举每一条从根节点到叶子节点的路径。当我们遍历到叶子节点，且此时target和当前节点值一致时，我们就找到了一条满足条件的路径。
注意，我们遍历完左右子树后，需要将记录的本节点从路径中删除
代码：
1public List<List<Integer>> pathSum(TreeNode root, int target) {
2 if (root == null) {
3 return new ArrayList<>();
4 }
5 List<List<Integer>> ansList = new ArrayList<>();
6 //路径数组
7 List<Integer> pathList = new ArrayList<>();
8 findTargetPath(root, target, ansList, pathList);
9 return ansList;
10}
11private void findTargetPath(TreeNode root, int target,
12 List<List<Integer>> ansList, List<Integer> pathList) {
13 if (root == null) {
14 return;
15 }
16 //本节点存入数组
17 pathList.add(root.val);
18 //target减去本节点
19 target -= root.val;
20 if (target == 0 && root.left == null && root.right == null) {
21 //target减去本节点为0 且本节点刚好为叶子节点，找到一条路径
22 ansList.add(new ArrayList<>(pathList));
23 }
24 //递归左右子树
25 findTargetPath(root.left, target, ansList, pathList);
26 findTargetPath(root.right, target, ansList, pathList);
27 //回溯、删除本节点
28 pathList.remove(pathList.size() - 1);
29}
时间复杂度：O(n * n) n为节点个数
空间复杂度：O(n)
方法二：父节点记录法
思路：
首先，咱们遍历一次二叉树，采用hash表记录每个节点和父节点的映射关系。同时，将父节点的值与本节点的值求和作为本节点的新值
之后，遍历hash中的每个节点，如果该节点的值和target一致，且其左右节点为空，表明该节点为符合要求的叶子节点。根据hash表，找到该节点到根节点的路径即可
代码：
1private void buildNode2Father(TreeNode root,
2 Map<TreeNode, TreeNode> node2Father) {
3 if (root == null) {
4 return;
5 }
6 //root节点就是父节点，将其左右子节点指向它即可
7 if (root.left != null) {
8 //将父节点的值与本节点的值求和作为本节点的新值
9 root.left.val = root.left.val + root.val;
10 node2Father.put(root.left, root);
11 //处理左子树为父节点的情况
12 buildNode2Father(root.left, node2Father);
13 }
14 if (root.right != null) {
15 //将父节点的值与本节点的值求和作为本节点的新值
16 root.right.val = root.right.val + root.val;
17 node2Father.put(root.right, root);
18 //处理右子树为父节点的情况
19 buildNode2Father(root.right, node2Father);
20 }
21}
22
23
24public List<List<Integer>> pathSum(TreeNode root, int target) {
25 if (root == null) {
26 return new ArrayList<>();
27 }
28 List<List<Integer>> ansList = new ArrayList<>();
29 //路径数组
30 List<Integer> pathList = new ArrayList<>();
31 findTargetPath(root, target, ansList, pathList);
32 return ansList;
33}
34private void findTargetPath(TreeNode root, int target,
35 List<List<Integer>> ansList, List<Integer> pathList) {
36 if (root == null) {
37 return;
38 }
39 //本节点存入数组
40 pathList.add(root.val);
41 //target减去本节点
42 target -= root.val;
43 if (target == 0 && root.left == null && root.right == null) {
44 //target减去本节点为0 且本节点刚好为叶子节点，找到一条路径
45 ansList.add(new ArrayList<>(pathList));
46 }
47 //递归左右子树
48 findTargetPath(root.left, target, ansList, pathList);
49 findTargetPath(root.right, target, ansList, pathList);
50 //回溯、删除本节点
51 pathList.remove(pathList.size() - 1);
52}
时间复杂度：O(n * n) n为节点个数
空间复杂度：O(n)
以上仅是个人思路解法，觉得还不错欢迎点赞关注分享
往期精彩推荐
算法和数据结构
IT程序员日常算法、数据结构分享
Official Account