回溯，树的遍历

题目链接-来源：力扣（LeetCode）

输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

示例:
给定如下二叉树，以及目标和 target = 22，

          5
         / \
        4   8
       /   / \
      11  13  4
     /  \    / \
    7    2  5   1

返回:

[
[5,4,11,2],
[5,8,4,5]
]

思路：

回溯算法的经典应用。我们需要从根节点开始遍历整棵树，统计当前路径上的和，同时用一个列表记录当前经历过的节点，并与target作比较，如果相等，就在结果列表中记录这个列表。每个节点都有左右两个子树，利用DFS，我们可以先递归遍历左子树，但是当该子树的递归返回的时候，我们要剪除其相关信息，因为这对我们遍历右子树没有帮助，之后，我们再递归地遍历右子树。这就是「回溯」。
时间复杂度：O(n)
空间复杂度：O(n)

实现：

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
class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        List<List<Integer>> ret = new ArrayList<>();
        List<Integer> tmp = new ArrayList<>();
        if (root != null) {
            DFS(root, target, 0, ret, tmp);
        }
        return ret;
    }
    
    private void DFS(TreeNode node, int target, int sum, List<List<Integer>> ret, List<Integer> pack) {
        sum += node.val;
        pack.add(node.val);
        if (sum == target && node.left == null && node.right == null) {
            ret.add(new ArrayList<Integer>(pack));
        }
        if (node.left != null) {
            DFS(node.left, target, sum, ret, pack);
        }
        
        if (node.right != null) {
            DFS(node.right, target, sum, ret, pack);
        }
        pack.remove(pack.size() - 1);
    }
}