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

June 普通 2023年9月17日下午3:18

/**
 * 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>> paths;
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        paths = new ArrayList<>();
        if (root == null)
            return paths;
        List<Integer> path = new ArrayList<>();
        dfs(root,target,0,path);
        return paths;
    }

    public void dfs(TreeNode node , int target , int sum, List<Integer> path) {
        sum += node.val;
        path.add(node.val);
        if(node.left == null && node.right == null)
        {
            if (sum == target)
                paths.add(new ArrayList<>(path)); //必须要复制
            path.remove(path.size()-1);
            return;
        }
        if(node.left != null)
            dfs(node.left,target,sum,path);
        if(node.right != null)
            dfs(node.right,target,sum,path);

        System.out.println(node.val);
        path.remove(path.size()-1);
    }
}

0 赞同 0 条回复

ppopp 普通 2023年9月10日上午11:02

/**
* 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> ret;
vector path;
vector<vector> pathSum(TreeNode root, int target) {
dfs(root, target);
return ret;
}

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

    //选择
    path.emplace_back(root->val);
    target -= root->val;

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

    //撤回选择
    path.pop_back();
}

};

0 赞同 0 条回复

Marshan 普通 2023年8月24日下午8:50

相对简单

class Solution {
public:
    vector<vector<int>> res;

    vector<vector<int>> pathSum(TreeNode* root, int target) {
        vector<int> trace;

        backTrace(root,trace,target);

        return res;
    }
    void backTrace(TreeNode *node,vector<int> &trace,int target){
        if(node == nullptr){
            return;
        }

        trace.push_back(node->val);
        if(sum(trace) == target && !node->left && !node->right){
            res.push_back(trace);
        }
        backTrace(node->left,trace,target);
        backTrace(node->right,trace,target);

        trace.pop_back();
    }
    int sum(vector<int> &trace){
        int sum = 0;
        for (int num : trace) {
            sum += num;
        }
        return sum;
    }
};

0 赞同 0 条回复

人生何处不青山普通 2023年8月23日上午12:02

简单题

function pathSum(root: TreeNode | null, target: number): number[][] {
    let result = [];
    const dfs = (node: TreeNode | null, sum: number, arr: number[]) => {
        if (!node) return;
        sum += node.val;
        arr.push(node.val);
        if (!node.left && !node.right) {
            if (sum === target) {
                result.push(arr.slice());
            }
            arr.pop();
            return;
        }
        dfs(node.left,sum,arr);
        dfs(node.right,sum,arr);
        arr.pop();
    }
    dfs(root,0,[]);
    return result;
};

0 赞同 0 条回复

mpweixin用户普通 2023年8月16日下午12:23

// 回溯+dfs
class Solution {
    private List<List<Integer>> res;
    private List<Integer> cur;
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        res = new ArrayList<>();
        cur = new ArrayList<>();
        dfs(root, target, 0);
        return res;
    }

    public void dfs(TreeNode root, int target, int curSum) {

        if(root==null) return;
        cur.add(root.val);
        if(curSum+root.val==target && root.left==null && root.right==null) {
            res.add(new ArrayList<>(cur));
        } else {
            dfs(root.left, target, curSum+root.val);
            dfs(root.right, target, curSum+root.val);
        }
        cur.remove(cur.size()-1);
        return;
    }
}

0 赞同 0 条回复

Mby 普通 2023年8月14日下午12:55

<pre><code class="line-numbers">/**
 * 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);
        //时间复杂度：O(n)
        //空间复杂度：O(n)
    }
}

</code></pre>

0 赞同 0 条回复

北辰普通 2023年8月11日下午4:50

class Solution {
    public List> res = new ArrayList>();
    public Deque path = new LinkedList();
    public List> pathSum(TreeNode root, int target) {
        dfs(root,target);
        return res;
    }

    private void dfs(TreeNode root,int target) {
        if(root==null) return;
        path.offerLast(root.val);
        target = target-root.val;
        if(root.left==null&&root.right==null&&target==0) {
            res.add(new LinkedList(path));
        }
        dfs(root.left,target);
        dfs(root.right,target);
        path.pollLast();
    }
}

时间复杂度：O（n^2)
空间复杂度：O（n)

0 赞同 0 条回复

#00456B 普通 2023年8月9日上午12:30

/**
 * 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>> pathSum(TreeNode* root, int target) {
        vector<vector<int>> ans;
        vector<int> temp;
        function<void(TreeNode*, int)> dfs = [&](TreeNode* root, int target)->void{
            if(root == nullptr){
                return ;
            }
            temp.push_back(root->val);
            target -= root->val;
            //当节点为叶子结点，且路径之和==target
            if(!root->left && !root->right && target == 0){
                ans.push_back(temp);
            }
            dfs(root->left, target);
            dfs(root->right, target);
            //回溯结束，弹出当前节点
            temp.pop_back();
        };
        dfs(root, target);
        return ans;
    }
};

0 赞同 0 条回复

NullPointerException 普通 2023年8月7日上午11:56

class Solution {
List<List> result =new ArrayList<List>();
public List<List> pathSum(TreeNode root, int target) {
//记录每一次走过 taeget – 当前 =0 并且是叶子可以加入
trck(root,target,new ArrayList());
return result;

}
public void trck(TreeNode root,int need,List<Integer> temp)
{
    if(root == null)
    {
        return ;
    }
    if(root.left==null &&root.right==null&&root.val==need)
    {
        temp.add(root.val);
        result.add(temp);
        return ;
    }
    temp.add(root.val);
    List<Integer> templeft= new ArrayList<Integer>(temp);
    List<Integer> tempright=new ArrayList<Integer>(temp);
    trck(root.left,need-root.val,templeft);
    trck(root.right,need-root.val,tempright);
}

}

0 赞同 0 条回复

长河呼叫黄江普通 2023年8月4日下午11:38

8.4
Day25：下面是代码

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

    //这里不能使用List<Integer>,否则path无法使用方法
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        recur(root, target);
        return res;
    }
    public void recur(TreeNode root, int target){
        if(root == null) return;
        path.add(root.val);
        target -= root.val;
        if(target == 0 && root.left == null && root.right == null){
            res.add(new LinkedList(path));
        }
        recur(root.left, target);
        recur(root.right, target);
        path.removeLast();

    }
}

0 赞同 0 条回复

阿尚普通 2023年8月4日下午5:06

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        if(root == null) return result;
        List<Integer> path = new ArrayList<>();

        getPath(root, target, path);

        return result;
    }

    public void getPath(TreeNode root, int target, List<Integer> path){
        path.add(root.val);
        target -= root.val;
        if(root.left == null && root.right == null && target == 0){
            result.add(new ArrayList<>(path));
            return;
        }

        if(root.left != null){
            getPath(root.left, target, path);
            path.remove(path.size() - 1);//回溯
        }
        if(root.right != null){
            getPath(root.right, target, path);
            path.remove(path.size() - 1);//回溯
        }
    }
}

0 赞同 0 条回复

AD钙奶普通 2023年8月4日下午2:59

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        if(root == null) {
            return res;
        }
        path.add(root.val);
        backTracking(root,target - root.val);
        return res;
    }

    public void backTracking(TreeNode root, int cnt) {
        // 边界
        if(root == null) return;
        if(root.left == null && root.right == null && cnt == 0) {
            res.add(new ArrayList<>(path));
            return ;
        }
        if(root.left != null) {
            // 逻辑
            path.add(root.left.val);
            cnt -= root.left.val;
            backTracking(root.left,cnt);
            // 回溯
            cnt += root.left.val;
            path.remove(path.size() - 1);
        }
        if(root.right != null) {
            // 逻辑
            path.add(root.right.val);
            cnt -= root.right.val;
            backTracking(root.right,cnt);
            // 回溯
            cnt += root.right.val;
            path.remove(path.size() - 1);
        }
    }
}

1 赞同 0 条回复

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

共以下 12 个回答

# 回答此问题取消回复

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

共以下 12 个回答

# 回答此问题 取消回复

# 回答此问题取消回复