一、题目

力扣原题：https://leetcode-cn.com/problems/path-sum-ii/

【二叉树】路径总和：https://blog.csdn.net/sinat_34596644/article/details/106109952

二、DFS+回溯

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

    private int target;

    private List<List<Integer>> result;

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        if (null == root) {
            return new ArrayList<>();
        }

        this.target = sum;
        this.result = new ArrayList<>();
        dfs(root, 0, new ArrayList<Integer>());
        return this.result;
    }

    private void dfs(TreeNode root, int cur, List<Integer> record) {
        if (null == root) {
            return;
        }

        // 记录当前状态
        cur = cur + root.val;
        record.add(root.val);

        // 1、当前路径和 = 目标路径和
        // 2、当前节点为叶子节点
        if (cur == this.target && null == root.left && null == root.right) {
            List<Integer> subResult = new ArrayList<>(record);
            this.result.add(subResult);
            return;
        }

        // 递归左子树
        if (null != root.left) {
            dfs(root.left, cur, record);
            record.remove(record.size() - 1);
        }

        // 递归右子树
        if (null != root.right) {
            dfs(root.right, cur, record);
            record.remove(record.size() - 1);
        }
    }
}

• 基本思路：相比于不记录路径的路径总和，需要多一个List保存结果。
• 时间复杂度：O(n)。DFS深度优先遍历，每个节点访问一次。
• 空间复杂度：O(log(n))。最坏情况是二叉树退化为链表，此时时间复杂度为O(n)，最好情况是最小的树深度O(log(n))。

三、总结

• 由于JAVA的引用传递，当找到目标节点时，需要基于当前的记录重新构造一个List，即List<Integer> subResult = new ArrayList<>(record);；
• 当DFS回溯到上一层时，需要将路径回退一格；

最后

以上就是有魅力狗为你收集整理的【二叉树】路径总和（含路径）一、题目二、DFS+回溯三、总结的全部内容，希望文章能够帮你解决【二叉树】路径总和（含路径）一、题目二、DFS+回溯三、总结所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。