二叉树算法实战：第 K 小元素与所有路径的 DFS 解法

关键点解析

代码中的 dfs 函数是核心。注意 if (--count == 0) 这一行，它利用了前置自减的特性，在递归左子树后立刻判断是否已找到目标。一旦满足条件，立即 return，后续的右子树遍历会被跳过，这就是剪枝的效果。

11. 二叉树的所有路径

题目链接

257. 二叉树的所有路径 - LeetCode

题目描述

题目示例

解题思路

这道题需要收集从根到叶子的所有路径，典型的深度优先搜索（DFS）+ 回溯场景。

路径以字符串形式构建，逻辑如下：

1. 递归入口：如果当前节点为空，直接返回。
2. 路径拼接：将当前节点值加入路径字符串。如果是叶子节点，说明一条完整路径结束，存入结果集；否则添加分隔符 "->" 继续递归左右子树。
3. 状态恢复：由于使用的是局部变量传递 path，每次递归调用结束后会自动回到上一层的状态，无需手动撤销操作，这比使用全局变量更简洁。

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:
    vector<string> ret; // 记录所有路径

    vector<string> binaryTreePaths(TreeNode* root) {
        string path; // 局部变量记录当前路径
        dfs(root, path);
        return ret;
    }

    void dfs(TreeNode* root, string path) {
        // 递归结束条件：节点为空
        if (root == nullptr) {
            return;
        }

        // 遇到叶子节点，路径结束
        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);
    }
};

关键点解析

这里有一个细节值得注意：path 作为参数传入是值传递（string），这意味着每一层递归都有自己独立的副本。当递归返回时，不需要像引用传递那样执行 pop_back 或截断字符串来'回溯'，因为上一层的 path 并没有被修改。这种写法让代码逻辑更清晰，减少了出错概率。

实际调试时，可以观察递归栈的变化，理解字符串是如何层层累积又自然释放的。