2021.10.4 力扣-路径总和及路径总和 II

路径总和题目描述：

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

方法一：

class Solution {
public:
    bool recur(TreeNode* cur, int targetSum, int sum)
    {
        if (cur == nullptr) return false;
        sum += cur->val;
        if (sum == targetSum && cur->left == nullptr && cur->right == nullptr) return true;
        return recur(cur->left, targetSum, sum) || recur(cur->right, targetSum, sum);
    }
    bool hasPathSum(TreeNode* root, int targetSum) {
        return recur(root, targetSum, 0);
    }
};

递归实现

路径总和 II题目描述：

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

方法一：

class Solution {
public:
    void dfs(TreeNode* cur, int targetSum, int sum, vector>& ans, vector& states)
    {
        if (cur == nullptr) return;
        sum += cur->val;
        states.push_back(cur->val);
        if (sum == targetSum && cur->left == nullptr && cur->right == nullptr)
        {
            ans.push_back(states);
            states.pop_back();
            return;
        }
        dfs(cur->left, targetSum, sum, ans, states);
        dfs(cur->right, targetSum, sum, ans, states);
        states.pop_back();
        return;
    }
    vector> pathSum(TreeNode* root, int targetSum) {
        vector> ans;
        vector states;
        dfs(root, targetSum, 0, ans, states);
        return ans;
    }
};

与一相比，这题需要找出并存储所有的可行路径，所以使用dfs回溯。