回溯 03

---

LeetCode 113

https://leetcode-cn.com/problems/path-sum-ii/

解题思路

标准的回溯

先dfs遍历下去，直到遇到叶子结点，然后判断一直到叶子结点的这条路径是否符合条件，不符合，则如果左右子树仍然存在，则继续遍历下去，直到树的最底层，（注：这里说的叶子结点比如图中的结点13，虽然它是叶子，但是还没有到树的最底层，依然可以继续往右遍历下去），最底层如果还是没法满足条件，则要回溯，把叶子结点在path路径中移除，寻找下一个可行解。

代码如下

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}
public class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        if (root == null) return new ArrayList<List<Integer>>();
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        List<Integer> path = new ArrayList<Integer>();
        dfs(res, path, root, sum, 0);
        return res;
    }

    public void dfs(List<List<Integer>> res, List<Integer> path, TreeNode root, int sum, int curSum) {
        if (root == null) return;
        curSum += root.val;
        path.add(root.val);
        if (curSum == sum && root.left == null && root.right == null) {
            // 这里必须要添加一个new的对象，不能直接把path添加进去
            // 引用一样，后面变动path就会跟着改变
            res.add(new ArrayList<>(path));
        } else {
            dfs(res, path, root.left, sum, curSum);
            dfs(res, path, root.right, sum, curSum);
        }
        // 递归完之后要回溯，把不符合条件的叶子结点移除path路径，继续寻找下一个可行解
        path.remove(path.size() - 1);
    }
}