很明显本题是一个回溯算法，解题的时候要注意，递归的下一句就是回溯。同时本题提供了两种不同的解法。
显式回溯 vs 隐式回溯
| 特性 | 隐式回溯 | 显式回溯写法 (vector<int> 或 string&) |
| 参数传递 | string path(值传递，拷贝) | vector<int>& path(引用传递) |
| 内存开销 | 较大。每层递归都要拷贝整个字符串。 | 较小。全程共用一个容器。 |
| 回溯操作 | 无。利用函数作用域自动销毁副本。 | 必须手动pop_back()。 |
| 代码示例 | traversal(node, path + "->", res) | path.push_back(val); traversal(...); path.pop_back(); |
| 理解难度 | 简单，符合直觉。 | 需要理解“恢复现场”的概念。 |
显式回溯
显式回溯将回溯的过程写了出来，比较容易理解。
tips：
- path使用整型数组是因为方便回溯。
- path和result是引用类，意味这整个递归全程共用一个容器。
- 使用先序遍历访问二叉树，是因为先序遍历符合二叉树的访问顺序。
- 根节点处理在递归结束条件前，是因为叶子节点也要加入path。
- 回溯就在递归的后面。
代码
void backtracking_1(TreeNode* root, vector<int>& path, vector<string>& result) { path.push_back(root->val); // 1. 处理当前节点 // 2. 判断叶子节点 if (root->left == nullptr && root->right == nullptr) { string sPath; for (int i = 0; i < path.size() - 1; i++) { sPath += to_string(path[i]); sPath += "->"; } sPath += to_string(path.back()); result.push_back(sPath); return; // 遇到叶子节点，记录路径后返回（注意：此时不pop，由调用层处理） } // 3. 递归逻辑 if (root->left) { backtracking_1(root->left, path, result); path.pop_back(); // 回溯：处理完左子树，把左孩子弹出，恢复现场 } if (root->right) { backtracking_1(root->right, path, result); path.pop_back(); // 回溯：处理完右子树，把右孩子弹出 } }显式回溯整体比较好理解。
隐式回溯
隐式回溯的核心在于利用 C++ 的“值传递” (Pass by Value) 特性。
- 引用传递 (&)：全程共享同一个 string 对象，子递归的修改会影响父递归，因此需要手动 pop_back 来“显式回溯”。
- 值传递 (无 &)：每次递归都会拷贝一份新的 string 副本。子递归只修改自己的副本，不影响父递归。
- 当子递归函数返回时，副本自动销毁，父递归的变量保持原样，从而实现了“隐式回溯”。
注意代码中的注释，解释为了为什么可以实现隐式回溯。
代码
void backtracking_2(TreeNode* root, string path, vector<string>& result){ // 这里修改的是本层的path值，也不会影响上一层的path值，但是会影响传递给下一层的path值 path += to_string(root->val); if(!root->left && !root->right){ result.push_back(path); return; } if(root->left){ // path + "->"：传递给下一层的path值为本层的path值加上"->",但是本层的path没有改变 backtracking_2(root->left, path + "->", result); } if(root->right){ backtracking_2(root->right, path + "->", result); } }拓展
当你理解了隐式回溯，下面的代码你应该也可以理解。
class Solution { private: void traversal(TreeNode* cur, string path, vector<string>& result) { path += to_string(cur->val); // 中，中为什么写在这里，因为最后一个节点也要加入到path中 if (cur->left == NULL && cur->right == NULL) { result.push_back(path); return; } if (cur->left) { path += "->"; traversal(cur->left, path, result); // 左 path.pop_back(); // 回溯 '>' path.pop_back(); // 回溯 '-' } if (cur->right) { path += "->"; traversal(cur->right, path, result); // 右 path.pop_back(); // 回溯'>' path.pop_back(); // 回溯 '-' } } public: vector<string> binaryTreePaths(TreeNode* root) { vector<string> result; string path; if (root == NULL) return result; traversal(root, path, result); return result; } };为什么这次path同样是值传递 (无 &)，但是也需要回溯，并需要回溯两次？
虽然这个代码也是值传递，但是在每一层path会执行“path += ”->", 并且将path传递给下一层，因此当下一层执行结束后，需要回溯将 “-” 和 “>" 回溯，
为什么不需要回溯节点的值？
因为是值传递 (无 &)，每层对于 “path += to_string(root->val);” 的操作是针对本层的path，不影响上一层path，只会影响下一层的传递，因此当本层执行完之后，返回上一层不需要回溯节点的值。
