九号球普通 2023年12月1日下午8:14

“`java
class Solution {
List> res;
int target;
public List> pathTarget(TreeNode root, int target) {
res = new ArrayList<>();
if (root == null) {
return res;
}
this.target = target;
List tmp = new ArrayList<>();
dfs(root, tmp);
return res;
}

public void dfs(TreeNode node, List<Integer> list) {
    if (node == null) {
        return;
    }
    list.add(node.val);
    //到达叶子节点，判断和是否等于target
    if (node.left == null && node.right == null) {
        int sum = 0;
        for (int i = 0; i < list.size(); i++) {
            sum += list.get(i);
        }
        if (sum == target) {
            List<Integer> resList = new ArrayList<>();
            resList.addAll(list);
            res.add(resList);
        }
        list.remove(list.size() - 1);
        return;
    }
    dfs(node.left, list);
    dfs(node.right, list);
    list.remove(list.size() - 1);
}

}

0 赞同 0 条回复

招舟子普通 2023年9月29日下午4:32

/**
* 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> res;
List tmp;
public List<List> pathTarget(TreeNode root, int target) {
res = new ArrayList<>();
tmp = new ArrayList<>();
dfs(root,target);
return res;
}
void dfs(TreeNode root, int target){
if(rootnull){
return;
}
tmp.add(root.val);
target = target-root.val;
if(root.rightnull&&root.leftnull&&target0){
res.add(new ArrayList<>(tmp));
}
dfs(root.left,target);
dfs(root.right,target);
tmp.remove(tmp.size()-1);
}
}
时间复杂度O（n）
空间复杂度O（n）

0 赞同 0 条回复

桀桀桀Jay 普通 2023年8月5日上午10:43

java
class Solution {
    private static int sum = 0;
    public List<List<Integer>> pathSum(TreeNode root, int target) {

        List<List<Integer>> res = new ArrayList<>();
        List<Integer> selected = new ArrayList<>();

        dfs(root, target, res, selected);
        return res;
    }

    public void dfs(TreeNode root, int target, List<List<Integer>> res, List<Integer> selected) {
        //遍历到空节点时
        if(root == null) {
            return;
        }
        //不是叶子节点，就将其加入到可选集中
        selected.add(root.val);
        target -= root.val;

        //如果没走到叶子节点时，sum就大于target了，说明后面的分支可以不用走下去了,剪枝,不行，忽略了负数
        // if(sum > target) {
        //     sum -= root.val;
        //     selected.remove(selected.size()-1);
        //     return;
        // }

        //如果满足一直走到叶子节点，且路径和等于目标，把该路径加入结果集中，终止条件
        if(root.left == null && root.right == null && target == 0) {
            res.add(new ArrayList<>(selected));
            /值得注意的是若是直接add(selected) 后续sel改变时，res中sel也会改变
            //正确做法是新建复制一份，耗了好久才发现
            selected.remove(selected.size()-1);
            sum -= root.val;
            return;
        }
        //递归左子树
        dfs(root.left, target, res, selected);
        //递归右子树
        dfs(root.right, target, res, selected);
        selected.remove(selected.size()-1);
        sum -= root.val;
        return;
    }
}

时间复杂度o(logn),kongjian o(n)

0 赞同 0 条回复

张开怀普通 2023年7月24日下午12:22

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

时间复杂度：O(n)
空间复杂度：O(n)

0 赞同 0 条回复

BOZ 普通 2023年7月20日上午11:34

【思路】回溯
【复杂度】时间复杂度O(n)，空间复杂度O(logn)

class Solution {
    vector<int> tmp;
    vector<vector<int>> result;

    void _pathSum(TreeNode* root, int target) {
        if (!root) return;

        tmp.push_back(root->val);
        if (!root->left && !root->right && root->val == target) result.push_back(tmp);
        if (root->left) _pathSum(root->left, target - root->val);
        if (root->right) _pathSum(root->right, target - root->val);
        tmp.pop_back();
    }

public:
    vector<vector<int>> pathSum(TreeNode* root, int target) {
        _pathSum(root, target);
        return result;
    }
};

0 赞同 0 条回复

怀瑾永久会员 2023年7月20日上午8:32

C++实现

“`C++
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

void dfs(TreeNode* node, int targetSum, int currentSum, vector& path,vector<vector>& result) {
if (!node) {
return;
}

currentSum += node->val;
path.push_back(node->val);

if (!node->left && !node->right && currentSum == targetSum) {
    result.push_back(path);
}

dfs(node->left, targetSum, currentSum, path, result);
dfs(node->right, targetSum, currentSum, path, result);

path.pop_back();

}

std::vector<std::vector> pathSum(TreeNode* root, int targetSum) {
std::vector<std::vector> result;
std::vector path;
dfs(root, targetSum, 0, path, result);
return result;
}

“`

0 赞同 0 条回复

局外人普通 2023年7月19日下午7:40

思路：DFS
时间复杂度：O(n) 空间复杂度：O(n)

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

    public void traverse(TreeNode root, int target){
        if(root==null)  return;


        track.add(root.val);
        trackSum += root.val;

        if(trackSum==target && root.left==null & root.right==null){
            res.add(new LinkedList(track)); //深拷贝！！！ 不new则属于浅拷贝
        }

        traverse(root.left, target);
        traverse(root.right, target);

        trackSum -= root.val;
        track.removeLast();

    }
}

0 赞同 0 条回复

花老爷普通 2023年7月19日下午5:01

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

class Solution {
    private List<List<Integer>> ans;

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

    private void dfs(int target, int sum, List<Integer> cur, TreeNode node) {
        cur.add(node.val);
        sum += node.val;
        if (node.left != null) {
            dfs(target, sum, cur, node.left);
        }
        if (node.right != null) {
            dfs(target, sum, cur, node.right);
        }        
        if (node.left == null && node.right == null && sum == target) {
            ans.add(new ArrayList<>(cur));
        }
        cur.remove(cur.size() - 1);
        sum -= node.val;
    }
}

0 赞同 0 条回复

Vow the vow。普通 2023年7月17日上午11:01

每次做，每次都不会系列

List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        dfs(new ArrayList<Integer>(), root, target);
        return res;
    }

    private void dfs(List<Integer> combine, TreeNode node, int need){
        if(node == null) return;
        combine.add(node.val);
        need -= node.val;
        if((node.left == null && node.right == null)  && need == 0){
            res.add(new ArrayList<>(combine));
        }
        dfs(combine, node.left, need);
        dfs(combine, node.right, need );
        combine.remove(combine.size()-1);
        need += node.val;

    }

0 赞同 0 条回复

mpweixin用户永久会员 2023年7月17日上午10:30

class Solution {
    List<List<Integer>> result = new ArrayList();
    List<Integer> curPath = new ArrayList();
    int sum = 0;

    public List<List<Integer>> pathSum(TreeNode root, int target) {
        if(root == null){
            return result;
        }

        dfs(root,target);

        return result;
    }
    void dfs(TreeNode root,int target){
        if(root == null){
            return;
        }
        //计算当前路径和
        curPath.add(root.val);
        sum += root.val;
        if((sum == target) && (root.left == null && root.right == null)){
            //确保等于target，且是“跟到叶子”
            result.add(new ArrayList(curPath));
        }

        //不等于target继续往下
        dfs(root.left,target);
        dfs(root.right,target);

        //回溯到自己
        curPath.remove(curPath.size() - 1);
        sum = sum - root.val;

    }
}

0 赞同 0 条回复

哈哈哈哈开开心心普通 2023年7月17日上午6:31

# Definition for a binary tree node.
# 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: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        res = []
        cur = []

        def dfs(root, target):
            if not root:
                return

            cur.append(root.val)
            target -= root.val

            if not root.left and not root.right and target == 0:
                res.append(cur.copy())

            dfs(root.left, target)
            dfs(root.right, target)

            cur.pop()
            target += root.val

            return

        dfs(root, targetSum)
        return res

本质回溯

0 赞同 0 条回复

yxy 普通 2023年7月16日下午7:46

时间复杂度O(n)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
    void backTrace(TreeNode* root, int target, vector<int>& path, int acc)
    {
        // if(acc>target)
        //     return;
        if(root)
        {
            path.push_back(root->val);
            acc+=root->val;
            cout<<acc<<endl;
            if(root->left==nullptr&&root->right==nullptr)
            {
                if(acc == target)
                    res.push_back(path);
                path.pop_back();
                return;
            }
            backTrace(root->left, target, path, acc);
            backTrace(root->right, target, path, acc);
            acc-=root->val;
            path.pop_back();
        }     
    }
    vector<vector<int>> res;
public:
    vector<vector<int>> pathSum(TreeNode* root, int target) {
        if(!root) return res;
        vector<int> path;
        backTrace(root, target, path, 0);
        return res;
    }
};

0 赞同 0 条回复

Yodl. 普通 2023年7月16日下午3:31

//时间复杂度O(n) 空间复杂度O(n) 
class Solution {
private:
    vector<int> path;                // 记录当前路径的一维数组
    vector<vector<int>> ans;         //要返回答案的二维数组
    void dfs(TreeNode* cur, int k){
        if(cur == nullptr) return;   //递归终止条件
        else {
            k-=cur->val;             //每走过一个非空节点，目标值减去这个节点的值
            path.push_back(cur->val);//记录这个节点
        } 

        if(k == 0 && cur->left == nullptr && cur->right == nullptr)
            ans.push_back(path);    //当k值0，且为叶子节点，也就是说该路径和刚好为目标值，加入答案
        dfs(cur->left, k);
        dfs(cur->right, k);
        path.pop_back();            //每回退一个节点，删除路径中该节点的记录
    }
public:
    vector<vector<int>> pathSum(TreeNode* root, int target) {
        dfs(root, target);          //递归搜索答案
        return ans;
    }
};

0 赞同 0 条回复

Dsjh 普通 2023年7月16日下午3:27

MY

class Solution {
public:
        vector<vector<int>> ans;
        vector<int> res;
    vector<vector<int>> pathSum(TreeNode* root, int target) {
        if(!root){
            return vector<vector<int>>{};
        }
        TreeNode* cur = root;
        dfs(cur,target);
        return ans;

    }
    void dfs(TreeNode* cur,int target){
        if(!cur){
            return;
        }
        res.push_back(cur->val);
        target -= cur->val;
        // 到达子节点
        if(!cur->left && !cur->right && target==0){
            ans.push_back(res);
        }
        dfs(cur->left,target);
        dfs(cur->right,target);
        res.pop_back();
    }
};

0 赞同 0 条回复

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

共以下 14 个回答

MY

# 回答此问题取消回复

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

共以下 14 个回答

MY

# 回答此问题 取消回复

# 回答此问题取消回复