LeetCode - [112、113]

一、LeetCode - 112. 路径总和；

路径总和：从根节点出发到叶子节点，为一条路径，将途经的节点值全部加起来，判断是否与targetSum相等

1 定义process函数，处理节点流程

node如果为叶子节点，表明一条路径已经到头了，判断是否节点值总和是否与targetSum相等；
如果是非叶子节点，则加上当前节点值，再调用process函数进行递归

public void process(TreeNode node, int preSum, int targetSum){
    if(node == null){
        if(preSum == targetSum){
            flag = true;
            return;
        }
    }
    //node为叶子节点
    if(node.left == null && node.right == null){
        if(preSum + node.val == targetSum){
            flag = true;
            return;
        }
    }
    //node为非叶子节点
    preSum += node.val;
    if(node.left != null){
        process(node.left, preSum, targetSum);
    }
    if(node.right != null){
        process(node.right, preSum, targetSum);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

2 全部代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

    public boolean flag = false;
    
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root == null){
            return false;
        }
        process(root, 0, targetSum);
        return flag;
    }
    public void process(TreeNode node, int preSum, int targetSum){
        if(node == null){
            if(preSum == targetSum){
                flag = true;
                return;
            }
        }
        //node为叶子节点
        if(node.left == null && node.right == null){
            if(preSum + node.val == targetSum){
                flag = true;
                return;
            }
        }
        //node为非叶子节点
        preSum += node.val;
        if(node.left != null){
            process(node.left, preSum, targetSum);
        }
        if(node.right != null){
            process(node.right, preSum, targetSum);
        }
    }
}
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

二、LeetCode - 113. 路径总和 II【进阶】

本题目在要求在找出是否有路径的基础上让我们找出所有可能的路径，并且放入一个List集合返回
首先，我们需要定义一个List list列表，用来存储我们path路径上经过的节点的值
其次，我们需要定义一个copy函数，用来复制list列表中的值，因为list是引用传递，如果直接传list会影响原来的值

1 process处理函数

public void process(TreeNode node, List<Integer> path, int preSum, int targetSum, List<List<Integer>> ans){
    //node为叶子节点
    if(node.left == null && node.right == null){
        if(preSum + node.val == targetSum){
            path.add(node.val);
            ans.add(copy(path));
            path.remove(path.size() - 1);
        }
        return;
    }
    //node为非叶子节点
    path.add(node.val);
    preSum += node.val;
    if(node.left != null){
        process(node.left, path, preSum, targetSum, ans);
    }
    if(node.right != null){
        process(node.right, path, preSum, targetSum, ans);      
    }
    path.remove(path.size() - 1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

1.1 node为叶子节点时

当node为叶子节点时，表明一条路径到了尽头，判断preSum（该路径之前经过的节点值总和） + node.val(当前节点的值) 是否等于 targetSum，如果等于，就将node.val添加进path（list集合），然后调用copy函数，复制list集合中的值，最后移除list集合中末尾的值【恢复现场，换另一条路，看看能否满足要求】

//node为叶子节点
if(node.left == null && node.right == null){
    if(preSum + node.val == targetSum){
        path.add(node.val);
        ans.add(copy(path));
        path.remove(path.size() - 1);
    }
    return;
}
1
2
3
4
5
6
7
8
9

1.2 node为非叶子节点时

当前node如果为非叶子节点，首先将node.val添加进path列表，同时更新preSum的值
判断：node.left与node.right是否为null，如果不为null，递归调用函数
整个函数最后需要恢复现场【移除path列表中最后的值】

//node为非叶子节点
path.add(node.val);
preSum += node.val;
if(node.left != null){
    process(node.left, path, preSum, targetSum, ans);
}
if(node.right != null){
    process(node.right, path, preSum, targetSum, ans);      
}
path.remove(path.size() - 1);
1
2
3
4
5
6
7
8
9
10

2 copy函数

public List<Integer> copy(List<Integer> path){
    List<Integer> list = new ArrayList<>();
    for(Integer i : path){
        list.add(i);
    }
    return list;
}
1
2
3
4
5
6
7

3 全部代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> ans = new ArrayList<>();
        if(root == null){
            return ans;
        }
        List<Integer> path = new ArrayList<>();
        process(root, path, 0, targetSum, ans);
        return ans;
    }
    public void process(TreeNode node, List<Integer> path, int preSum, int targetSum, List<List<Integer>> ans){
        //node为叶子节点
        if(node.left == null && node.right == null){
            if(preSum + node.val == targetSum){
                path.add(node.val);
                ans.add(copy(path));
                path.remove(path.size() - 1);
            }
            return;
        }
        //node为非叶子节点
        path.add(node.val);
        preSum += node.val;
        if(node.left != null){
            process(node.left, path, preSum, targetSum, ans);
        }
        if(node.right != null){
            process(node.right, path, preSum, targetSum, ans);      
        }
        path.remove(path.size() - 1);
    }
    public List<Integer> copy(List<Integer> path){
        List<Integer> list = new ArrayList<>();
        for(Integer i : path){
            list.add(i);
        }
        return list;
    }
}
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
55