【算法】递归(成员变量和按值传递的不同用法)

例题1：

解法一：path作为成员变量传递，需要回溯。

classSolution{intaim,path,ret;public:intfindTargetSumWays(vector<int>&nums,inttarget){aim=target;dfs(nums,0);returnret;}voiddfs(vector<int>&nums,intpos){if(pos==nums.size()){if(path==aim)ret++;return;}path+=nums[pos];dfs(nums,pos+1);path-=nums[pos];path-=nums[pos];dfs(nums,pos+1);path+=nums[pos];}};

解法二：path作为参数传递下去，每层递归会自动帮我们回溯（函数压栈的原理）

classSolution{intaim,ret;public:intfindTargetSumWays(vector<int>&nums,inttarget){aim=target;dfs(nums,0,0);returnret;}voiddfs(vector<int>&nums,intpos,intpath){if(pos==nums.size()){if(path==aim)ret++;return;}dfs(nums,pos+1,path+nums[pos]);dfs(nums,pos+1,path-nums[pos]);}};

注意:当所有递归层需要维护同一份路径，或者复制成本较高时最好设为成员变量。
当变量数据较小，而且每条递归路径都需要独立副本时，适合按值传递。

例题二：

解法一：成员变量

classSolution{vector<string>ret;string path;public:vector<string>binaryTreePaths(TreeNode*root){if(root==nullptr)returnret;dfs(root);returnret;}voiddfs(TreeNode*root){size_t oldSize=path.size();path+=to_string(root->val);if(root->left==nullptr&&root->right==nullptr){ret.push_back(path);path.resize(oldSize);return;}path+="->";if(root->left)dfs(root->left);if(root->right)dfs(root->right);path.resize(oldSize);}};

解法二：按值传递

classSolution{vector<string>ret;public:vector<string>binaryTreePaths(TreeNode*root){if(root==nullptr)returnret;string path;dfs(root,path);returnret;}voiddfs(TreeNode*root,string path){path+=to_string(root->val);if(root->left==nullptr&&root->right==nullptr){ret.push_back(path);return;}path+="->";if(root->left)dfs(root->left,path);if(root->right)dfs(root->right,path);}};