剑指 Offer 34 二叉树中和为某一值的路径

概述

https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/

https://leetcode.com/problems/path-sum-ii/

回溯法

class Solution {
public:
    vector<vector<int>> ans;
    int targetSum;
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        if (!root) return ans;
        this-> targetSum = targetSum;
        vector<int> path = {root->val};
        backtrack(root, path, root->val);
        return ans;
    }
    
    void backtrack(TreeNode* root, vector<int>& path, int currentSum) {
        if (!root->left && !root->right) {
            if (currentSum == targetSum) {
                ans.push_back(path);
                return;
            }
        }
        if (root->left) {
            path.push_back(root->left->val);
            backtrack(root->left, path, currentSum + root->left->val);
            path.pop_back();
        }
        if (root->right) {
            path.push_back(root->right->val);
            backtrack(root->right, path, currentSum + root->right->val);
            path.pop_back();            
        }
    }
};

Links: sword-offer-34

未经允许，禁止转载，本文源站链接：https://iamazing.cn/