题目描述（中等难度）

“>112 题 的基础上改了，解法没有新内容，大家可以过去看一看。

解法一 递归

public boolean hasPathSum(TreeNode root, int sum) { if (root == null) { return false; } return hasPathSumHelper(root, sum); } private boolean hasPathSumHelper(TreeNode root, int sum) { //到达叶子节点 if (root.left == null && root.right == null) { return root.val == sum; } //左孩子为 null if (root.left == null) { return hasPathSumHelper(root.right, sum - root.val); } //右孩子为 null if (root.right == null) { return hasPathSumHelper(root.left, sum - root.val); } return hasPathSumHelper(root.left, sum - root.val) || hasPathSumHelper(root.right, sum - root.val); }

这里的话我们需要一个ans变量来保存所有结果。一个temp变量来保存遍历的路径。需要注意的地方就是，java中的list传递的是引用，所以递归结束后，要把之前加入的元素删除，不要影响到其他分支的temp。

public List<List<Integer>> pathSum(TreeNode root, int sum) {

    List<List<Integer>> ans = new ArrayList<>();
    if (root == null) {
        return ans;
    }
    hasPathSumHelper(root, sum, new ArrayList<Integer>(), ans);
    return ans;
}

private void hasPathSumHelper(TreeNode root, int sum, ArrayList<Integer> temp, List<List<Integer>> ans) {
    // 到达叶子节点
    if (root.left == null && root.right == null) {
        if (root.val == sum) {
            temp.add(root.val);
            ans.add(new ArrayList<>(temp));
            temp.remove(temp.size() - 1);
        }
        return;
    }
    // 左孩子为 null
    if (root.left == null) {
        temp.add(root.val);
        hasPathSumHelper(root.right, sum - root.val, temp, ans);
        temp.remove(temp.size() - 1);
        return;
    }
    // 右孩子为 null
    if (root.right == null) {
        temp.add(root.val);
        hasPathSumHelper(root.left, sum - root.val, temp, ans);
        temp.remove(temp.size() - 1);
        return;
    }
    temp.add(root.val);
    hasPathSumHelper(root.right, sum - root.val, temp, ans);
    temp.remove(temp.size() - 1);

    temp.add(root.val);
    hasPathSumHelper(root.left, sum - root.val, temp, ans);
    temp.remove(temp.size() - 1);
}

“>112 题 利用栈实现的DFS。

看一下之前用后序遍历实现的代码。

public boolean hasPathSum(TreeNode root, int sum) {
    List<Integer> result = new LinkedList<>();
    Stack<TreeNode> toVisit = new Stack<>();
    TreeNode cur = root;
    TreeNode pre = null;
    int curSum = 0; //记录当前的累计的和
    while (cur != null || !toVisit.isEmpty()) {
        while (cur != null) {
            toVisit.push(cur); // 添加根节点
            curSum += cur.val;
            cur = cur.left; // 递归添加左节点
        }
        cur = toVisit.peek(); // 已经访问到最左的节点了
        //判断是否满足条件
        if (curSum == sum && cur.left == null && cur.right == null) {
            return true;
        }
        // 在不存在右节点或者右节点已经访问过的情况下，访问根节点
        if (cur.right == null || cur.right == pre) {
            TreeNode pop = toVisit.pop();
            curSum -= pop.val; //减去出栈的值
            pre = cur;
            cur = null;
        } else {
            cur = cur.right; // 右节点还没有访问过就先访问右节点
        }
    }
    return false;
}

和解法一一样，我们需要ans变量和temp变量，同样需要注意temp是对象，是引用传递。

public List<List<Integer>> pathSum(TreeNode root, int sum) {
    Stack<TreeNode> toVisit = new Stack<>();
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> temp = new ArrayList<>();
    TreeNode cur = root;
    TreeNode pre = null;
    int curSum = 0; // 记录当前的累计的和
    while (cur != null || !toVisit.isEmpty()) {
        while (cur != null) {
            toVisit.push(cur); // 添加根节点
            curSum += cur.val;
            /************修改的地方******************/
            temp.add(cur.val);
            /**************************************/
            cur = cur.left; // 递归添加左节点
        }
        cur = toVisit.peek(); // 已经访问到最左的节点了
        // 判断是否满足条件
        if (curSum == sum && cur.left == null && cur.right == null) {
            /************修改的地方******************/
            ans.add(new ArrayList<>(temp));
            /**************************************/
        }
        // 在不存在右节点或者右节点已经访问过的情况下，访问根节点
        if (cur.right == null || cur.right == pre) {
            TreeNode pop = toVisit.pop();
            curSum -= pop.val; // 减去出栈的值
            /************修改的地方******************/
            temp.remove(temp.size() - 1);
            /**************************************/
            pre = cur;
            cur = null;
        } else {
            cur = cur.right; // 右节点还没有访问过就先访问右节点
        }
    }
    return ans;
}

总

和