【LeetCode-113 | 路径总和II】

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>

using namespace std;


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>> result;
    vector<int> path;
    /* 因为要遍历整棵树，找到所有路径;因此,递归函数不需要返回值 */
        
        // 1.确定递归函数的入参及返回值
    void Traversal(TreeNode* node, int count) {
        // 2.确定递归终止条件
        // 遇到了叶子节点且找到了和为sum的路径
        if(!node->left && !node->right && count == 0) {
            result.push_back(path);
            return ;   
        }
        // 遇到叶子节点但没有找到和为sum的路径
        if(!node->left && !node->right) return ;

        // 3.确定单层递归逻辑
        if(node->left) {
            path.push_back(node->left->val);
            count -= node->left->val;
            Traversal(node->left, count);  // 递归
            count += node->left->val;  // 回溯
            path.pop_back();   // 回溯

        }

        if(node->right) {
            path.push_back(node->right->val);
            count -= node->right->val;
            Traversal(node->right, count);  // 递归
            count += node->right->val;   // 回溯
            path.pop_back();   // 回溯
        }
        return ;

    }

    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        if(root == nullptr) return result;

        path.push_back(root->val);
        Traversal(root, targetSum - root->val);
        return result;
    }
};