1+ // 113. 路径总和 II
2+
3+
4+ /**
5+ * Definition for a binary tree node.
6+ * public class TreeNode {
7+ * int val;
8+ * TreeNode left;
9+ * TreeNode right;
10+ * TreeNode() {}
11+ * TreeNode(int val) { this.val = val; }
12+ * TreeNode(int val, TreeNode left, TreeNode right) {
13+ * this.val = val;
14+ * this.left = left;
15+ * this.right = right;
16+ * }
17+ * }
18+ */
19+
20+
21+ /*
22+ 递归，回溯：
23+ 1、成员变量 res 存放结果路径，path 存放搜索过程路径
24+ 2、定义递归函数
25+ 1）方法功能：入参是节点、目标和，将节点值接入path列表，当节点为叶子结点 且 节点值等于目标和，则将路径加入res结果列表。处理结果加入列表即可，不需要返回
26+ 2）终止条件：节点为空时，结束
27+ 3）递归逻辑：左右节点同样需要加入路径、判断目标和，因此调用同样的方法实现递归处理。当前节点递归处理完成后需要从路径中移除节点值，即回溯，不影响其他路径的递归处理
28+ */
29+ class Solution {
30+ private List <List <Integer >> res = new ArrayList <>();
31+ private List <Integer > path = new ArrayList <>();
32+
33+ public List <List <Integer >> pathSum (TreeNode root , int targetSum ) {
34+ dfs (root , targetSum );
35+ return res ;
36+ }
37+
38+ private void dfs (TreeNode root , int targetSum ) {
39+ if (root == null ) {
40+ return ;
41+ }
42+ path .add (root .val );
43+ if (root .left == null && root .right == null && root .val == targetSum ) {
44+ res .add (new ArrayList <>(path ));
45+ }
46+ targetSum -= root .val ;
47+ dfs (root .left , targetSum );
48+ dfs (root .right , targetSum );
49+ path .remove (path .size () - 1 );
50+ }
51+ }
52+
53+
54+ /*
55+ 广度优先搜索：
56+ 1、成员变量 res 存放结果路径；map存放 {节点:父节点} 关系，用于根据叶子结点找出整条路径
57+ 2、层序遍历节点，利用两个队列分别保存 节点 和 到达节点时的路径和
58+ 3、当节点是叶子节点时，判断路径和等于目标和则获取路径加入res结果列表中。
59+ 否则将左右节点与其对应的路径和加入队列中，并且保存左右节点与父节点的关系到map中，然后继续循环处理
60+ 4、最后返回res结果列表
61+ */
62+ class Solution {
63+ private List <List <Integer >> res = new ArrayList <>();
64+ private Map <TreeNode , TreeNode > map = new HashMap <>();
65+
66+ public List <List <Integer >> pathSum (TreeNode root , int targetSum ) {
67+ if (root == null ) {
68+ return res ;
69+ }
70+ Queue <TreeNode > nodeQueue = new LinkedList <>();
71+ Queue <Integer > sumQueue = new LinkedList <>();
72+ nodeQueue .add (root );
73+ sumQueue .add (root .val );
74+ while (!nodeQueue .isEmpty ()) {
75+ TreeNode node = nodeQueue .poll ();
76+ Integer sum = sumQueue .poll ();
77+ if (node .left == null && node .right == null && sum == targetSum ) {
78+ getPath (node );
79+ }
80+ if (node .left != null ) {
81+ nodeQueue .add (node .left );
82+ sumQueue .add (sum + node .left .val );
83+ map .put (node .left , node );
84+ }
85+ if (node .right != null ) {
86+ nodeQueue .add (node .right );
87+ sumQueue .add (sum + node .right .val );
88+ map .put (node .right , node );
89+ }
90+ }
91+ return res ;
92+ }
93+
94+ private void getPath (TreeNode node ) {
95+ List <Integer > path = new ArrayList <>();
96+ while (node != null ) {
97+ path .add (0 , node .val );
98+ node = map .get (node );
99+ }
100+ res .add (new ArrayList <>(path ));
101+ }
102+ }
0 commit comments