【回溯专题】剑指 Offer 34. 二叉树中和为某一值的路径-跟着帅地玩副业，开拓第二曲线PlayOffer

陆狗陆狗普通 2024年12月24日下午7:36

解题思路
– 使用递归进行回溯（就是下一步进行不同的选择，比如当前节点的下一步是左子树还是右子树）
– 关键在于设计dfs函数的定义。dfs(TreeNode next, int sum, List sumList)。一定要想清楚，当前的next和sum，sumList是什么状态进来的？
– 应该是sum还没有加next的值，sum是sumList的值之和
【题解1】dfs，自己的解法，还有改进空间

class Solution {

    List<List<Integer>> result;
    int target;

    public List<List<Integer>> pathTarget(TreeNode root, int target) {
        result = new ArrayList();
        this.target = target;
        if (root == null) {
            return result;
        }
        dfs(root, 0, new ArrayList<>());
        return result;
    }

    // 一定要想清楚，当前的next和sum，sumList是什么状态进来的？
    // 应该是sum还没有加next的值，sum是sumList的值之和
    public void dfs(TreeNode next, int sum, List<Integer> sumList) {
        // next不可能是null，因为根节点为null已经调用前返回了
        sum = sum + next.val;
        // 当前节点是叶子结点
        sumList.add(next.val);
        if (next.left == null && next.right == null) {
            if (sum == target) {
                result.add(sumList);
            }
            return;
        }

        // 当前节点不是叶子结点
        // 【错误点】val可以正数可以负数，所以不能用sum>target 提前返回，会导致二叉树-1，-2这种出现错误
        // if (sum > target) {
        //     // 结果已经大于目标值了
        //     return;
        // }
        // 判断到底左子树还是右子树有值，注意必须重新给一个sumList，因为sumList不是全局唯一的
        if (next.left != null) {
            dfs(next.left, sum, new ArrayList<>(sumList));
        }
        if (next.right != null) {
            dfs(next.right, sum, new ArrayList<>(sumList));
        }

    }
}

错误点1：val可以正数可以负数，所以不能用sum>target 提前返回

【题解2】dfs，参考的题解，这个写法节约了一些内存空间

class Solution {

    List<List<Integer>> result = new ArrayList();
    int target;

    public List<List<Integer>> pathTarget(TreeNode root, int target) {
        result = new ArrayList();
        this.target = target;
        dfs(root, 0, new ArrayList<>());
        return result;
    }

    // 一定要想清楚，当前的next和sum，sumList是什么状态进来的？
    // 应该是sum还没有加next的值，sum是sumList的值之和
    public void dfs(TreeNode next, int sum, List<Integer> sumList) {
        // 【改进点1】判空，如果是叶子结点的null，不进行任何的操作；如果root就是null也不进行任何操作
        if (next == null) {
            return;
        }
        // 追加元素
        sum = sum + next.val;
        sumList.add(next.val);
        // 当前节点是叶子结点
        if (sum == target && next.left == null && next.right == null) {
            // 【改进点2】真正需要添加到result的时候才new，这样可以节约内存
            result.add(new ArrayList(sumList));
        }
        // 不用判断是否叶子结点，因为dfs方法开头会判空，直接返回
        dfs(next.left, sum, sumList);
        dfs(next.right, sum, sumList);
        // 【改进点2】移除元素，能保证sumList的复用
        sumList.removeLast();
    }
}

改进点1：判空，这样可以不管左右叶子节点的left和right是不是null，都可以去执行一次dfs方法，能让代码看着简洁一点
改进点2：之前的写法为了防止ArrayList数据混乱，是每一次调用dfs都需要new ArrayList，导致内存使用较大；现在的改进方法是，在本层次先加元素，执行完毕后，再删除掉尾部的元素，这样回缩到上一层的时候还是干净的。只需要在result.add的时候new一下即可。

0 赞同 0 条回复

Xiang. 永久会员 2024年12月23日上午11:38

class Solution {
    List<List<Integer>> res;
    List<Integer> tmp;
    public List<List<Integer>> pathTarget(TreeNode root, int target) {
        this.res=new ArrayList<>();
        this.tmp=new ArrayList<>();
        dsf(root,target);
        return res;
    }
    void dsf(TreeNode root,int target){
        if(root==null) return;
        target=target-root.val;
        tmp.add(root.val);
        if(root.left==null&&root.right==null&&target==0){
            res.add(new ArrayList(tmp));
        }
        dsf(root.left,target);
        dsf(root.right,target);
        tmp.remove(tmp.size()-1);

    }
时间复杂度：O（n）
空间复杂度：O（n）

0 赞同 0 条回复

秋山丽奈普通 2024年12月21日下午3:29

思路：回溯

class Solution {
    List<TreeNode> nodeList = new ArrayList<>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();

    public List<List<Integer>> pathTarget(TreeNode root, int target) {

        find(root, target, 0);
        return ans;
    }

    public void find(TreeNode node, int target, int current){
        if(node == null){
            return;
        }

        if(current + node.val == target && node.left == node.right){
            nodeList.add(node);
            List<Integer> nodeVal = new ArrayList<>();
            for(TreeNode currentNode: this.nodeList){
                nodeVal.add(currentNode.val);
            }

            ans.add(nodeVal);
            // 对应删除 
            nodeList.remove(nodeList.size()-1);
        }else{
            // 将当前节点加入 
            nodeList.add(node);
            find(node.left, target, current + node.val);
            find(node.right, target, current + node.val);
            // 对应删除 
            nodeList.remove(nodeList.size()-1);
        }
    }
}

0 赞同 0 条回复

Kisara 普通 2024年12月19日下午6:12

有一两个需要注意的点
1. 不能直接添加path到结果数组，因为java中数组名是一个引用，要复制一个集合加入result
2. 结束条件不是target=0而是target=root.val

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List> result=new ArrayList<>();
    List path=new ArrayList<>();
    public List> pathTarget(TreeNode root, int target) {
        dfs(root,target);
        return result;
    }


public void dfs(TreeNode root,int target){
    if(root==null) return;
    path.add(root.val);
    if(target==root.val&&root.left==null&&root.right==null) result.add(new ArrayList<>(path));

    dfs(root.left,target-root.val);
    dfs(root.right,target-root.val);

    path.remove(path.size()-1);
}

}

On O logn+L×logn

0 赞同 0 条回复

Aatorx 永久会员 2024年12月19日下午3:49

class Solution {
public:
    vector<vector<int>> res;
    vector<int> v;
    vector<vector<int>> pathTarget(TreeNode* root, int target) {
        dfs(root, target);
        return res;
    }
    void dfs(TreeNode* root, int target) {
        if(!root) {
            return;
        }
        target -= root->val;
        v.push_back(root->val);
        if (target == 0 && !root->left && !root->right) {
            res.push_back(v);
        }
        dfs(root->left, target);
        dfs(root->right, target);
        target += root->val;
        v.pop_back();
    }
};

优先深度搜索。
时间复杂度O(N)，空间复杂度O(N)。

0 赞同 0 条回复

月下足迹普通 2024年12月19日上午10:40

//先序遍历二叉树+回溯记录路径

class Solution {
LinkedList<List> res = new LinkedList<>();
LinkedList path = new LinkedList<>();
public List<List> pathTarget(TreeNode root, int target) {
recur(root, target);
return res;
}
void recur(TreeNode root, int tar) {
if(root null) return;
path.add(root.val);
tar -= root.val;
if(tar 0 && root.left null && root.right null)
res.add(new LinkedList(path));
recur(root.left, tar);
recur(root.right, tar);
path.removeLast();
}
}

0 赞同 0 条回复

苯庸普通 2024年12月19日上午10:23

class Solution {
List<List> res = new ArrayList();
List path = new ArrayList();
public List<List> pathTarget(TreeNode root, int target) {
dfs(root, target, 0);
return res;
}

void dfs(TreeNode root, int target, int cur){
    if(root == null) return;
    path.add(root.val);
    cur += root.val;
    if(root.left == null && root.right == null && cur == target){
        res.add(new ArrayList(path));
    }
    dfs(root.left, target, cur);
    dfs(root.right, target, cur);
    path.remove(path.size()-1);
    cur -= root.val;
}

}
时间：O（n）
空间：O（n）

0 赞同 0 条回复

Jerry 普通 2024年12月18日下午8:16

class Solution {
public:
    vector<vector<int>> res;
    vector<vector<int>> pathTarget(TreeNode* root, int target) {
        if(!root) return res;
        vector<int> oneres;
        oneres.push_back(root->val);
        dfs(root, target, oneres, root->val);
        return res;
    }
    //明确函数定义：进入函数时，oneres已经包含了root节点，且root->val已经记入sum！
    void dfs(TreeNode* root, int target, vector<int>& oneres, int sum){
        if(!root) return;
        if(!root->left && !root->right){
            if(sum == target) res.push_back(oneres);
            return;
        }
        if(root->left){
            oneres.push_back(root->left->val);
            dfs(root->left, target, oneres, sum + root->left->val);
            oneres.pop_back();

        }
        if(root->right){
            oneres.push_back(root->right->val);
            dfs(root->right, target, oneres, sum + root->right->val);
            oneres.pop_back();
        }
        return;
    }
};

时间o（n）n是二叉树的节点个数
空间o（n）
注意点：明确函数定义：进入函数时，oneres已经包含了root节点，且root->val已经记入sum！
明确了再写

0 赞同 0 条回复

【回溯专题】剑指 Offer 34. 二叉树中和为某一值的路径

共以下 8 个回答

# 回答此问题取消回复

【回溯专题】剑指 Offer 34. 二叉树中和为某一值的路径

共以下 8 个回答

# 回答此问题 取消回复

# 回答此问题取消回复