leetcode113 路径总和2 特别关注

 1 /*
 2  * @lc app=leetcode.cn id=113 lang=cpp
 3  *
 4  * [113] 路径总和 II
 5  */
 6 
 7 // @lc code=start
 8 /**
 9  * Definition for a binary tree node.
10  * struct TreeNode {
11  *     int val;
12  *     TreeNode *left;
13  *     TreeNode *right;
14  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
15  * };
16  */
17 class Solution {
18 public:
19     vector<vector<int>> res;
20     vector<vector<int>> pathSum(TreeNode* root, int sum) {
21         if(root==nullptr) return res;
22         vector<int> temp;
23         helper(root,sum, temp);
24         return res;
25     }
26 //注意这里没有显示的指定终止递归的条件，但是在达到叶子节点时，会隐式终止递归并返回上一层，也就是回溯到上一层
27     void helper(TreeNode* root,int sum, vector<int>&　temp){
28         temp.push_back(root->val);//加入决策路径，注意这里没有显示的指定递归的终止条件
29 
30         if(!root->left&&!root->right&&sum==root->val){
31             res.push_back(temp);
32         }
33 
34         if(root->left) helper(root->left,sum-root->val, temp);
35         if(root->right) helper(root->right,sum-root->val, temp);
36         //到达叶子节点时，没有找到可行解，该决策移除决策路径
37         temp.pop_back();
38     }
39 
40 
41     // 逻辑清晰的版本，回溯，递归一起用，
42     //什么时候递归函数不需要返回值
43     // vector<vector<int>> res;
44     // vector<int> path;
45     // // 递归函数不需要返回值，因为我们要遍历整个树
46     // void traversal(TreeNode* cur,int count){
47     //     if(!cur->left&&!cur->right&&count==0) {// 遇到了叶子节点切找到了和为sum的路径
48     //         res.push_back(path);
49     //         return ;
50     //     }
51 
52     //     if(cur->left){
53     //         path.push_back(cur->left->val);
54     //         count-=cur->left->val;
55     //         traversal(cur->left,count);// 递归
56     //         count+=cur->left->val;// 回溯
57     //         path.pop_back();// 回溯
58     //     }
59 
60     //     if(cur->right){
61     //         path.push_back(cur->right->val);
62     //         count-=cur->right->val;
63     //         traversal(cur->right,count);
64     //         count+=cur->right->val;
65     //         path.pop_back();
66     //     }
67 
68     //     return ;
69     // }
70     // vector<vector<int>> pathSum(TreeNode* root, int sum) {
71     //     if(root==nullptr) return res;
72     //     path.push_back(root->val);// 把根节点放进路径
73     //     traversal(root, sum-root->val);
74     //     return res;
75     // }
76 };
77 // @lc code=end