LeetCode_七贤镇

1、题目：二叉树的所有路径

给你一个二叉树的根节点 root，按任意顺序，返回所有从根节点到叶子节点的路径。
叶子节点是指没有子节点的节点。

【LeetCode】
2、解题思路方法一：递归递归三步曲
1、递归函数函数参数以及返回值，要传入根节点，记录每一条路径的path，和存放结果集的result，这里递归不需要返回值
2、确定递归终止条件，当 cur不为空，其左右孩子都为空的时候，就找到叶子节点。

//终止处理逻辑if (cur->left == NULL && cur->right == NULL) { // 遇到叶子节点string sPath;for (int i = 0; i < path.size() - 1; i++) { // 将path里记录的路径转为string格式sPath += to_string(path[i]);sPath += "->";}sPath += to_string(path[path.size() - 1]); // 记录最后一个节点（叶子节点）result.push_back(sPath); // 收集一个路径return;}

3、确定单层递归逻辑，回溯和递归是一一对应的，有一个递归，就要有一个回溯，不能把递归和回溯拆开了，一个在花括号里，一个在花括号外。

if (cur->left) {traversal(cur->left, path, result);path.pop_back(); // 回溯}if (cur->right) {traversal(cur->right, path, result);path.pop_back(); // 回溯}

方法二：迭代每次进去循环都进行，要么往下寻找一格，要么回退一格。
3、代码

//递归class Solution {private:void traversal(TreeNode* cur, vector& path, vector& result) {path.push_back(cur->val);// 这才到了叶子节点if (cur->left == NULL && cur->right == NULL) {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 binaryTreePaths(TreeNode* root) {vector result;vector path;if (root == NULL) return result;traversal(root, path, result);return result;}};

//迭代class Solution {public:vector binaryTreePaths(TreeNode* root) {stack treeSt;// 保存树的遍历节点stack pathSt;// 保存遍历路径的节点vector result;// 保存最终路径集合if (root == NULL) return result;treeSt.push(root);pathSt.push(to_string(root->val));while (!treeSt.empty()) {TreeNode* node = treeSt.top(); treeSt.pop(); // 取出节点 中string path = pathSt.top();pathSt.pop();// 取出该节点对应的路径if (node->left == NULL && node->right == NULL) { // 遇到叶子节点result.push_back(path);}if (node->right) { // 右treeSt.push(node->right);pathSt.push(path + "->" + to_string(node->right->val));}if (node->left) { // 左treeSt.push(node->left);pathSt.push(path + "->" + to_string(node->left->val));}}return result;}};