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

白雪公主倒拔垂杨柳永久会员 2024年4月2日下午1:42

class Solution {
    List<List<Integer>> res;
    List<Integer> tmp;

    public List<List<Integer>> pathTarget(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.right==null && root.left==null && target==0){
            res.add(new ArrayList<>(tmp));
        }
        dfs(root.right,target);
        dfs(root.left,target);
        tmp.remove(tmp.size()-1);
    }
}

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

0 赞同 0 条回复

Thaddeus 永久会员 2024年3月31日上午9:04

打卡

class Solution {
public:
    vector<vector<int>> pathTarget(TreeNode* root, int target) {
        if(!root) return res;
        dfs(root, target);
        return res;
    }
private:
    void dfs(TreeNode* root, int target) {
        if(!root) return;
        path.emplace_back(root->val);
        if(!root->left && !root->right && root->val == target) {
            res.emplace_back(path);
            // return;
        }

        dfs(root->left, target - root->val);
        dfs(root->right, target - root->val);
        path.pop_back(); // 每层只需pop一次，因为只push了一次
    }
private:
    vector<int> path;
    vector<vector<int>> res;
};

0 赞同 0 条回复

heathhou 普通 2024年3月30日下午9:41

/**
 * 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 {
public:
    vector<vector<int>> pathTarget(TreeNode* root, int target) {
        if(root == nullptr){
            return{};
        }
        dfs(root, target);
        return res;
    }

    void dfs(TreeNode* root, int target){
        if(root == nullptr){
            return;
        }
        tmp.push_back(root->val);
        target -= root->val;
        if(root->left == nullptr && root->right == nullptr && target == 0){
            res.push_back(tmp);
        }
        dfs(root->left, target);
        dfs(root->right, target);
        tmp.pop_back();
    }


private:
    vector<vector<int>> res;
    vector<int> tmp;
};

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

0 赞同 0 条回复

紫芝普通 2024年3月30日上午12:40

思路：二叉树dfs

“`c++
/**
* 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 {
public:
void dfs(vector> &ans, vector current, TreeNode* cur, int sum, int target) {
if (cur == nullptr) return;

    sum += cur->val;
    current.push_back(cur->val);
    if (cur->left == nullptr && cur->right == nullptr) {
        if (sum == target) {
            ans.push_back(current);
        }
    }
    dfs(ans, current, cur->left, sum, target);
    dfs(ans, current, cur->right, sum, target);
}
vector<vector<int>> pathTarget(TreeNode* root, int target) {
    vector<vector<int>> ans;
    vector<int> temp;
    dfs(ans, temp, root, 0, target);
    return ans;
}

};

“`

0 赞同 0 条回复

王位詮釋普通 2024年3月29日下午10:01

自己写的，改了好几次才全过了，思路：使用回溯法，递归访问节点，如果一个节点不为空的话就代表可以访问，否则不可以访问，如果访问了之后刚好这个节点是叶子节点且满足target，那我们就记录下这个结果（这里一定要记录result的副本而不是result本身），否则继续向下递归遍历自己的左右子节点。思路其实本质就是深度优先搜索。
class Solution {
    List<List<Integer>> results = new ArrayList<>();
    List<Integer> result = new ArrayList<>();
    public List<List<Integer>> pathTarget(TreeNode root, int target) {
        backtrace(root,target,0);
        return results;
    }
    public void backtrace(TreeNode root,int target,int sum){
        if(root==null){
            return;
        }
        sum+=root.val;
        result.add(root.val);
        if(sum==target){
            if(root.left==null&&root.right==null){
                results.add(new ArrayList(result));
                result.remove(result.size()-1);
                return;
            }
        }
        TreeNode[] children = new TreeNode[]{root.left,root.right};
        for(TreeNode node:children){
            backtrace(node,target,sum);
        }
        sum-=root.val;
        result.remove(result.size()-1);
    }
}
帅地的方法：
我的思路和帅地的思路一样，但是帅地的代码更简洁，更容易理解：
class Solution {
    List<List<Integer>> results = new ArrayList<>();
    List<Integer> result = new ArrayList<>();
    public List<List<Integer>> pathTarget(TreeNode root, int target) {
        backtrace(root,target);
        return results;
    }
    public void backtrace(TreeNode root,int target){
        if(root==null){
            return;
        }
        target-=root.val;
        result.add(root.val);
        if(target==0&&root.left==null&&root.right==null){
            results.add(new ArrayList(result));
        }
        backtrace(root.left,target);
        backtrace(root.right,target);
        result.remove(result.size()-1);
    }
}

0 赞同 0 条回复

机电皮怪永久会员 2024年3月29日下午2:15

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

“`C++
class Solution {
public:
vector> pathTarget(TreeNode* root, int target) {
vector> res;
vector tmp;

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

    dfs(root, target);
    return res;
}

};

“`

0 赞同 0 条回复

方铎码农普通 2024年3月29日下午1:17

/**
 * 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;
 *     }
 * }
 */
//由于需要找到所有路径，本次使用回溯法，使用可改变的List path作为回溯数组
class Solution {
    LinkedList<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        recur(root,targetSum);
        return res;
    }

    void recur (TreeNode root, int targetSum) {
        if(root == null) return;
        path.add(root.val);
        targetSum -= root.val;
        if(targetSum == 0 && root.left == null && root.right == null) 
            res.add(new LinkedList<Integer>(path));
        recur(root.left, targetSum);
        recur(root.right, targetSum);
        path.removeLast(); 
    }
}

回溯算法，注意这个算法是在二叉树一般递归算法的基础上，将存储路径的List变成了可复用的回溯栈，空间复杂度降低为$O(m)$（m为树的最大深度），空间复杂度$O(n)$

0 赞同 0 条回复

云无深雁影普通 2024年3月29日上午9:43

/**
* 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 {
public List<List> pathTarget(TreeNode root, int target) {
return path(root,target);
}
private List<List> path(TreeNode node,int target){
List<List> path = new ArrayList<>();
if(node null )
return path;
if(target – node.val 0 && node.left null && node.right null){
List p = new ArrayList<>();
p.addFirst(node.val);
path.add(p);
return path;
}
List<List> lpath = path(node.left ,target – node.val);
if(lpath!=null){
for(int i = 0; i < lpath.size(); i++){
lpath.get(i).addFirst(node.val);
path.addFirst(lpath.get(i));
}
}
List<List> rpath = path(node.right ,target – node.val);
if(rpath!=null){
for(int i = 0; i < rpath.size(); i++){
rpath.get(i).addFirst(node.val);
path.addFirst(rpath.get(i));
}
}
return path;
}
}
//空间复杂度O(n)
//时间复杂度O(n)

0 赞同 0 条回复

Raphtalia. 普通 2024年3月28日下午11:58

/**
* 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 {
public:
vector<vector> pathTarget(TreeNode root, int target) {
dfs(root, target);
return res;
}
private:
vector path;
vector<vector> res;
void dfs(TreeNode* root, int target) {
if(root nullptr) return;
path.push_back(root->val);
target -= root->val;
if(root->left nullptr && root->right nullptr && target 0) {//叶子节点
res.push_back(path);
}
dfs(root->left, target);
dfs(root->right, target);
path.pop_back();
}
};

0 赞同 0 条回复

Jimmy 普通 2024年3月28日下午8:15

使用深度优先搜索，下面代码的第7行是回溯目标值，没有这一行也可以得到正确答案，这是为什么？
这是因为在这段代码中，目标值 target 是通过函数参数传递给递归调用的 dfs 函数的。每次递归调用时，都会创建一个新的函数调用栈帧，其中包含了当前的 target 值。而在回溯的过程中，每次递归调用返回时，函数调用栈帧也会被弹出，从而恢复到上一层节点的状态，包括了目标值 target。因此，即使在回溯的过程中没有手动恢复目标值 target，它也会在函数调用栈的机制下自动地恢复到正确的状态。
尽管在这个特定的情况下不添加 target += root->val 这一行代码也能得到正确的答案，但在一般情况下，为了代码的健壮性和可读性，最好在回溯的过程中手动恢复相关的状态。这可以确保代码的正确性，并且使得代码更容易理解和维护。

/**
 * 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 {
public:
    vector> res;
    vector temp;
    vector> pathTarget(TreeNode* root, int target) {
        dfs(root,target);
        return res;
    }

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

        temp.push_back(root->val);
        target -= root->val;
        if(!root->left && !root->right && target == 0)
        {
            res.push_back(temp);
        }
        dfs(root->left,target);
        dfs(root->right,target);
        temp.pop_back();
        target += root->val;

    }
};

0 赞同 0 条回复

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

共以下 10 个回答

# 回答此问题取消回复

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

共以下 10 个回答

# 回答此问题 取消回复

# 回答此问题取消回复