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

例题1解法一path作为成员变量传递需要回溯。classSolution{intaim,path,ret;public:intfindTargetSumWays(vectorintnums,inttarget){aimtarget;dfs(nums,0);returnret;}voiddfs(vectorintnums,intpos){if(posnums.size()){if(pathaim)ret;return;}pathnums[pos];dfs(nums,pos1);path-nums[pos];path-nums[pos];dfs(nums,pos1);pathnums[pos];}};解法二path作为参数传递下去每层递归会自动帮我们回溯函数压栈的原理classSolution{intaim,ret;public:intfindTargetSumWays(vectorintnums,inttarget){aimtarget;dfs(nums,0,0);returnret;}voiddfs(vectorintnums,intpos,intpath){if(posnums.size()){if(pathaim)ret;return;}dfs(nums,pos1,pathnums[pos]);dfs(nums,pos1,path-nums[pos]);}};注意:当所有递归层需要维护同一份路径或者复制成本较高时最好设为成员变量。当变量数据较小而且每条递归路径都需要独立副本时适合按值传递。例题二解法一成员变量classSolution{vectorstringret;string path;public:vectorstringbinaryTreePaths(TreeNode*root){if(rootnullptr)returnret;dfs(root);returnret;}voiddfs(TreeNode*root){size_t oldSizepath.size();pathto_string(root-val);if(root-leftnullptrroot-rightnullptr){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{vectorstringret;public:vectorstringbinaryTreePaths(TreeNode*root){if(rootnullptr)returnret;string path;dfs(root,path);returnret;}voiddfs(TreeNode*root,string path){pathto_string(root-val);if(root-leftnullptrroot-rightnullptr){ret.push_back(path);return;}path-;if(root-left)dfs(root-left,path);if(root-right)dfs(root-right,path);}};