网站访客qq统计系统百度搜索app

原题链接：113.路径总和II
需复刷

思路：
跟112.路径总和不同，该题是要你找出所有相同的路径，那么此时就要注意存储，递归和回溯了。

全代码：

class Solution {
public:vector<vector<int>> result;vector<int> path;// 递归函数不需要返回值，因为我们要遍历整个树void traversal(TreeNode* cur, int count) {if (!cur->left && !cur->right && count == 0) { // 遇到了叶子节点且找到了和为sum的路径result.push_back(path);return;}if (!cur->left && !cur->right) return ; // 遇到叶子节点而没有找到合适的边，直接返回if (cur->left) { // 左 （空节点不遍历）path.push_back(cur->left->val);count -= cur->left->val;traversal(cur->left, count);    // 递归count += cur->left->val;        // 回溯path.pop_back();                // 回溯}if (cur->right) { // 右 （空节点不遍历）path.push_back(cur->right->val);count -= cur->right->val;traversal(cur->right, count);   // 递归count += cur->right->val;       // 回溯path.pop_back();                // 回溯}return ;}vector<vector<int>> pathSum(TreeNode* root, int targetSum) {result.clear();path.clear();if (root == NULL) return result;path.push_back(root->val); // 把根节点放进路径traversal(root, targetSum - root->val);return result;}
};