二叉搜索树中第 k 小的元素与二叉树的所有路径算法解析

算法总结及流程解析：

11. 二叉树的所有路径

题目链接：

257. 二叉树的所有路径 - 力扣（LeetCode）

题目描述：

题目示例：

解法：回溯

算法思路：

使用深度优先遍历 (DFS) 求解。路径以字符串形式存储，从根节点开始遍历，每次遍历时将当前节点的值加入到路径中，如果该节点为叶子节点，将路径存储到结果中。否则，将 "->" 加入到路径中并递归遍历该节点的左右子树。

定义一个结果数组，进行递归。递归具体实现方法如下:

1. 如果当前节点不为空，就将当前节点的值加入路径 path 中，否则直接返回；
2. 判断当前节点是否为叶子节点，如果是，则将当前路径加入到所有路径的存储数组 path 中;
3. 否则，将当前节点值加上 "->" 作为路径的分隔符，继续递归遍历当前节点的左右子节点；
4. 返回结果数组。

特别地，我们可以只使用一个字符串存储每个状态的字符串，在递归回溯的过程中，需要将路径中的当前节点移除，以回到上一个节点。

C++ 算法代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    // 用全局变量 ret 记录所有路径，全局不会受到递归回溯的影响
    vector<string> ret;
    vector<string> binaryTreePaths(TreeNode* root) {
        string path; // 用局部变量 path 记录路径的值，不用全局变量是为了便于回溯时'恢复原状'
        dfs(root, path);
        return ret;
    }
    void dfs(TreeNode* root, string path) {
        // 递归的结束条件：当前结点为空则结束递归进行返回
        if(root == nullptr) {
            return;
        }
        // 当遇到叶子结点时则不用再添加箭头，并且此时一条路径已经结束，
        // 用 string 数组 ret 进行记录并且直接返回
        if(root->left == nullptr && root->right== nullptr) {
            path += to_string(root->val);
            ret.push_back(path);
            return;
        }
        // 前序遍历
        path += to_string(root->val);
        path += "->";
        dfs(root->left, path);
        dfs(root->right, path);
    }
};

算法总结及流程解析：