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

Gg 普通 2023年8月2日下午11:19

/**
 * 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 {
    private List<List<Integer>> res;
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        res = new ArrayList<>();
        traverse(new ArrayList<>(),root,0,target);
        return res;

    }

    public void traverse(List<Integer> currList, TreeNode curr, int currSum, int target){
        if(curr == null){
            return;
        }
        // 考虑当前节点
        currList.add(curr.val);
        currSum += curr.val;
        // 满足条件加入最终结果
        if(currSum == target && curr.left == null && curr.right == null){
            List<Integer> success = List.copyOf(currList);
            res.add(success);
        }
        traverse(currList,curr.left,currSum,target);
        traverse(currList,curr.right,currSum,target);
        // 移除当前节点
        currList.remove(currList.size()-1);


    }
}

0 赞同 0 条回复

宁永久会员 2023年3月14日上午10:46

注意深拷贝和浅拷贝之间的区别！

class Solution {
    //结果列表
    //每一个结果在函数内部添加
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> selectList = new LinkedList<>();

    public List<List<Integer>> pathSum(TreeNode root, int target) {
        if(root == null) return new ArrayList<>();
        backTracing(root, target);
        return res;
    }
    public void backTracing(TreeNode node, int target){
        if(node == null){
            return;
        }
        //这一步处理的是node节点
        selectList.add(node.val);
        target = target - node.val;
        if(target == 0 && node.left == null && node.right == null){
            //深拷贝和浅拷贝
            res.add(new ArrayList<>(selectList));
        }
        backTracing(node.left, target);
        backTracing(node.right, target);
        selectList.removeLast();
    }
}

0 赞同 0 条回复

PatNick 普通 2023年1月17日下午8:44

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def pathSum(self, root: TreeNode, target: int) -> list[list[int]]:
        result = []
        temp = []
        def dfs(node):

            if not node:
                return

            temp.append(node.val)
            if sum(temp) == target and not node.right and not node.left:
                # 这里不可以直接将temp append到result中，后面temp的改变会使result也改变
                result.append([_ for _ in temp])
            dfs(node.left)
            dfs(node.right)
            # 回溯时消除上一个节点的元素
            temp.pop(-1)



        dfs(root)
        return result



    # 优化：将target设成动态的new_target -= node.val，来避免每次遍历都需要对temp求和，这样到遍历到叶子节点的时候，如果new_target==0,说明满足temp=target
    def pathSum1(self, root: TreeNode, target: int) -> list[list[int]]:
        result = []
        temp = []

        def dfs(node, new_target):

            if not node:
                return

            temp.append(node.val)
            new_target -= node.val
            if not node.right and not node.left and new_target == 0:
                result.append([_ for _ in temp])

            dfs(node.left, new_target)
            dfs(node.right, new_target)
            temp.pop(-1)

        dfs(root, target)
        return result

0 赞同 0 条回复

lucca 普通 2023年1月16日下午8:33

DFS

时间复杂度 O(N)
空间复杂度 O(N)

class Solution {

    private List<List<Integer>> ans = new LinkedList<>();

    public List<List<Integer>> pathSum(TreeNode root, int target) {
        if (root == null) return ans;
        LinkedList<Integer> li = new LinkedList<Integer>();
        dfs(root, li, target);
        return ans;
    }

    private void dfs(TreeNode root, LinkedList<Integer> li, int target) {
        if (root == null || Math.abs(target - root.val) < 0) return;

        li.add(root.val);
        target -= root.val;

        if (root.left == null && root.right == null) {
            if (target == 0) ans.add(new ArrayList<>(li));
            li.removeLast();
            return;
        }

        dfs(root.left, li, target);
        dfs(root.right, li, target);
        li.removeLast();
    }
}

0 赞同 0 条回复

@ 普通 2022年12月14日上午10:34

时间复杂度：O(N)

空间复杂度：O(N)

class Solution {
    List<List<Integer>> res = new ArrayList<>();

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

        List<Integer> list = new ArrayList<>();
        dfs(root, target, 0, list);
        return res;
    }

    public void dfs(TreeNode root, int target, int sum, List<Integer> list) {
        if (root == null)
            return;

        sum += root.val;

        //一定要开辟一个新的list，如果还是继续用原有的list的话，这个list是会随着递归而不断改变的
        List<Integer> cur = list.stream().collect(Collectors.toList());


        //注意： 是从根节点到叶子节点路径，到中间的不算，所以要加上 root.left == null && root.right == null
        if (sum == target && root.left == null && root.right == null) {
            cur.add(root.val);
            res.add(cur);
            return;
        }

        cur.add(root.val);

        dfs(root.left, target, sum, cur);
        dfs(root.right, target, sum, cur);


    }

}

0 赞同 0 条回复

🚲南下普通 2022年12月3日下午5:56

class Solution {
public:
    vector<int> path;
    vector<vector<int>> ret;
    void dfs(TreeNode* root,int target){ //深度优先搜索
        if(root==nullptr) return;

        path.push_back(root->val);
        target-=root->val;
        if(target==0&&root->left==nullptr&&root->right==nullptr) ret.push_back(path);
        dfs(root->left,target);
        dfs(root->right,target);
        path.pop_back();
    }

    vector<vector<int>> pathSum(TreeNode* root, int target) {
        dfs(root,target);
        return ret;
    }
};

0 赞同 0 条回复

你有点可爱喔普通 2022年12月3日下午5:03

/**
 * 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<List<Integer>> res;
    List<Integer> tmp;
    public List<List<Integer>> pathSum(TreeNode root, int target) {
            //给定的和 = 根——子节点；返回结点
            res = new ArrayList<>();
            tmp = new ArrayList<>();
            dfs(root,target);
            return res;
    }
    void dfs(TreeNode root,int target){

        if(root == null){
            return;
        }

        tmp.add(root.val); //接收根节点的值
        target = target-root.val;
        //子节点为空
        if (root.left == null && root.right == null && target == 0){
            res.add(new ArrayList<>(tmp));
        }
        dfs(root.left,target);
        dfs(root.right,target);
        tmp.remove(tmp.size()-1);

    }
}

0 赞同 0 条回复

T 普通 2022年11月30日下午3:52

下面代码

class Solution {
    LinkedList<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        backtrace(root, 0, target);
        return res;
    }

    void backtrace(TreeNode root, int sum, int target) {
        if(root == null) return;
        path.add(root.val);
        sum += root.val;
        if(sum == target && root.left == null && root.right == null) {
            res.add(new LinkedList<>(path));
        }
        backtrace(root.left, sum, target);
        backtrace(root.right, sum, target);
        path.removeLast();
    }
}

0 赞同 0 条回复

庄重普通 2022年11月24日下午3:31

//  思路：
//     1.深度搜索需要对target值进行减少，直至到叶子节点的时候target值为0
class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int target) {
        if(root == NULL) 
            return res;
        dsf(root,target);
        return res;
    }
private:
    void dsf(TreeNode* root, int target){
        if(root == NULL)
            return;

        target -= root->val;
        tmp.push_back(root->val);
        if(root->left == NULL && root->right == NULL && target == 0){
            res.push_back(tmp);
        }
        dsf(root->left,target);
        dsf(root->right,target);
        //需要抓住回溯得位置
        tmp.pop_back();
        return;
    }
    vector<vector<int>> res;
    vector<int> tmp;
};
//时间复杂度O(n) n为节点个数
//空间复杂度O(n)

0 赞同 0 条回复

西西弗斯的石头永久会员 2022年11月23日下午5:31

时间空间复杂度都为O（n）

class Solution {
    List<List<Integer>> list;
    List<Integer> list1;
    public List<List<Integer>> pathSum(TreeNode root, int target) {
         list = new ArrayList<>();
         list1 = new ArrayList<>();
         f(root,target);
         return list;
    }
    void f(TreeNode root, int target){
        if(root == null) return;
        list1.add(root.val);
        target  = target - root.val;
        if(root.left == null && root.right == null && target == 0) list.add(new ArrayList<>(list1));
        f(root.left,target);
        f(root.right,target);
        list1.remove(list1.size() - 1);
    }
}

0 赞同 0 条回复

So 普通 2022年11月22日下午6:41

/**
 * 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<List<Integer>> res;
    List<Integer> temp;
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        res = new ArrayList<>();
        temp = new ArrayList<>();
        dsf(root, target);
        return res;
    }

    void dsf(TreeNode root, int target) {
        if (root == null) {
            return;
        }
        temp.add(root.val);
        target = target - root.val;
        if (root.left == null && root.right == null && target == 0) {
            res.add(new ArrayList<>(temp));
        }
        dsf(root.left, target);
        dsf(root.right, target);
        temp.remove(temp.size() - 1);
    }
}

时间：O(n^2)，空间：O(n)

0 赞同 0 条回复

Tolkien 永久会员 2022年11月22日下午12:54

public class Solution {
    private static List<List<Integer>> RESULT;
    private static List<Integer> SELECTED_NODE;

    public List<List<Integer>> pathSum(TreeNode root, int target) {
        RESULT = new ArrayList<>();
        SELECTED_NODE = new ArrayList<>();

        dfs(root, target);
        return RESULT;
    }

    private void dfs(TreeNode root, int target) {
        // 终止条件：到达叶子节点
        if (root == null) {
            return;
        }

        // 选择此阶段其中一个解，将其加入到已选解集合中
        SELECTED_NODE.add(root.val);
        target = target - root.val;

        // 若满足条件，则将其加入结果集
        if (root.left == null && root.right == null && target == 0) {
            RESULT.add(new ArrayList<>(SELECTED_NODE));
        }

        // 进入下一阶段
        dfs(root.left, target);
        dfs(root.right, target);

        // 回溯
        SELECTED_NODE.remove(SELECTED_NODE.size()-1);
    }
}

0 赞同 0 条回复

訁訁訁訁訁普通 2022年11月21日下午11:33

回溯
时间复杂度O(N)
空间复杂度最差为O(N)
class Solution {
    LinkedList<Integer> path = new LinkedList<Integer>();
    List<List<Integer>> ret = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        backtracking(root,target);
        return ret;
    }
    void backtracking(TreeNode root,int target){
        if(root == null) return ;
        path.addLast(root.val);
        target = target - root.val;
        if(target == 0 && root.left == null && root.right == null){
            ret.add(new ArrayList(path));
        }
        backtracking(root.left,target);
        backtracking(root.right,target);
        path.removeLast();
    }
}

0 赞同 0 条回复

Error 普通 2022年11月21日下午11:03

class Solution:
    def pathSum(self, root: TreeNode, target: int) -> List[List[int]]:
        res = []
        path = []
        def recur(root, tar):
            if not root:
                return
            s = tar - root.val
            path.append(root.val)
            if s == 0 and not root.left and not root.right:
                res.append(list(path))
            recur(root.left, s)
            recur(root.right, s)
            path.pop()
        recur(root, target)
        return res

时间复杂度 log(n)

0 赞同 0 条回复

y 普通 2022年11月21日下午10:28

//cnt 等于目标和  如果最后cnt == 0，同时到了叶子节点的话，说明找到了目标和。
var pathSum = function(root, target) {
    let res = [];
   const travelsal = (cnt, node, path) => {
       if (cnt === 0 && !node.left && !node.right) {
           res.push([...path]);
           return;
       }
    //    遍历到叶子节点没有符合的
       if (!node.left && !node.right) return;

       if (node.left) {
         path.push(node.left.val);
         cnt -= node.left.val;
         travelsal(cnt, node.left, path);
         cnt += node.left.val; // 回溯
         path.pop(); //回溯
       }

       if (node.right) {
           path.push(node.right.val);
           cnt -= node.right.val;
           travelsal(cnt, node.right, path);
           cnt += node.right.val; //回溯
           path.pop() //回溯
       }
       return;
   }
   if(!root) return res;
   travelsal(target - root.val, root, [root.val]);
   return res;
};

0 赞同 0 条回复

青木普通 2022年11月21日下午10:16

/**
    很像前序遍历的递归写法

    时间O(n^2)
    空间O(logn)
 */

class Solution {
    List<List<Integer>> lists;
    List<Integer> list;
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        this.lists = new LinkedList<>();
        this.list = new LinkedList<>();
        preorder(root, target);
        return lists;
    }

    public void preorder(TreeNode node, int target){
        if(node == null) return;
        list.add(node.val);
        if(node.left == null && node.right == null && target == node.val){
            lists.add(new LinkedList<>(list));
        }
        preorder(node.left, target - node.val);
        preorder(node.right, target - node.val);
        list.remove(list.size() - 1);
    }
}

0 赞同 0 条回复

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

共以下 16 个回答

DFS

# 回答此问题取消回复

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

共以下 16 个回答

DFS

# 回答此问题 取消回复

# 回答此问题取消回复