一、题意
二、思考过程
这道题涉及到两个概念：
- 路径
- 回溯
需要用到的是 前序遍历，通过前序遍历，父节点到叶子节点之后形成路径,将每一条路径转换为串并存到结果集中result中，回溯以后再次重复形成其他路径，进入其他路径，path短暂存放这些路径元素，前序遍历以及回溯过程如下：
我们先使用递归的方式做前序遍历，然后进行回溯！
2.1递归三部曲：
- 递归函数的参数和返回值
void traversal(TreeNode* cur, vector<int>& path, vector<string>& result) //path:路径 //result：存放结果集
- 确定终止条件
if (cur->left == NULL && cur->right == NULL) { //找到叶子节点，把路径放到result结果集里 }
- 单层递归逻辑
因为是前序遍历，需要先处理中间节点，中间节点就是我们要记录的路径上的节点，先放进path中。
path.push_back(cur->val);//中间节点
递归和回溯的过程：
if (cur->left) { traversal(cur->left, path, result); path.pop_back(); // 回溯 } if (cur->right) { traversal(cur->right, path, result); path.pop_back(); // 回溯 }
完整代码：
class Solution { private: void traversal(TreeNode* cur, vector<int>& path, vector<string>& result) { path.push_back(cur->val);//中间节点 // 这才到了叶子节点 if (cur->left == NULL && cur->right == NULL) {//将path里的记录路径转换为sting string sPath; for (int i = 0; i < path.size() - 1; i++) { sPath += to_string(path[i]); sPath += "->"; } sPath += to_string(path[path.size() - 1]);//记录最后一个节点，叶子结点 result.push_back(sPath);//收集一个路径 return; } if (cur->left) { traversal(cur->left, path, result); path.pop_back(); // 回溯 } if (cur->right) { traversal(cur->right, path, result); path.pop_back(); // 回溯 } } public: vector<string> binaryTreePaths(TreeNode* root) { vector<string> result; vector<int> path; if (root == NULL) return result; traversal(root, path, result); return result; } };
