题目描述

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

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

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

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

题解

回溯法

这道题明显可以通过回溯算法进行遍历求解, 就是先序遍历+路径记录

首先考虑递归的终止条件, 需要注意的是题目中描述只有到达叶子节点才算一条完整的路径, 所以不必考虑路径中途停止的情况, 直接将终止条件设置成root == null即可, 表示已经遍历穿了.

终止条件: root== null, 直接返回
*递归过程: *
1. 路径更新: 将当前的节点值加入路径中
2. 目标更新: 将当前的目标值减去当前的节点值
3. 判断路径是否满足条件: 若当前节点为叶子节点并且目标值为0, 则将当前路径加入到res 列表中.
4. 遍历左右子节点
5. 路径恢复

值得注意的是，记录路径时若直接执行 res.append(path) ，则是将 path 对象加入了 res ；后续 path 改变时， res 中的 path 对象也会随之改变。

正确做法：res.append(list(path)) ，相当于复制了一个 path 并加入到 res 。

public class jz34 {
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        recur(root, sum);
        return res;
    }

    private void recur(TreeNode root, int target) {

        if (root == null)
            return;
        path.addLast(root.val);
        target -= root.val;
        if (target == 0 && root.left == null && root.right == null) {
            res.add(new ArrayList<>(path));
        }
        recur(root.left, target);
        recur(root.right, target);
        path.removeLast();

    }
}