二叉树--所有路径

很明显本题是一个回溯算法，解题的时候要注意，递归的下一句就是回溯。同时本题提供了两种不同的解法。

显式回溯 vs 隐式回溯

显式回溯

显式回溯将回溯的过程写了出来，比较容易理解。

tips：

1. path使用整型数组是因为方便回溯。
2. path和result是引用类，意味这整个递归全程共用一个容器。
3. 使用先序遍历访问二叉树，是因为先序遍历符合二叉树的访问顺序。
4. 根节点处理在递归结束条件前，是因为叶子节点也要加入path。
5. 回溯就在递归的后面。

代码

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) 特性。

1. 引用传递 (&)：全程共享同一个 string 对象，子递归的修改会影响父递归，因此需要手动 pop_back 来“显式回溯”。
2. 值传递 (无 &)：每次递归都会拷贝一份新的 string 副本。子递归只修改自己的副本，不影响父递归。
3. 当子递归函数返回时，副本自动销毁，父递归的变量保持原样，从而实现了“隐式回溯”。

注意代码中的注释，解释为了为什么可以实现隐式回溯。

代码

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，只会影响下一层的传递，因此当本层执行完之后，返回上一层不需要回溯节点的值。