二叉树深度优先搜索（DFS）核心算法与实战

二、求根节点到叶节点数字之和

题目链接：https://leetcode.cn/problems/sum-root-to-leaf-numbers/

思路解析

这道题需要构建从根到叶的路径字符串，将其转换为整数后累加。关键在于如何在递归过程中传递当前的累积值。

1. 参数设计：dfs(node, currentSum)，其中 currentSum 记录到达当前节点前的路径数值。
2. 更新数值：每进入一个节点，新值为 currentSum * 10 + node->val。
3. 终止条件：当遇到叶子节点时，返回当前累积值；否则继续向左右子树传递。

代码实现

class Solution {
public:
    int dfs(TreeNode* root, int preNum) {
        // 更新当前路径代表的数值
        int nowNum = preNum * 10 + root->val;
        
        // 叶子节点返回累积值
        if (!root->left && !root->right) return nowNum;
        
        int ret = 0;
        // 递归处理左右子树
        if (root->left) ret += dfs(root->left, nowNum);
        if (root->right) ret += dfs(root->right, nowNum);
        
        return ret;
    }
    
    int sumNumbers(TreeNode* root) {
        return dfs(root, 0);
    }
};

三、二叉树剪枝

题目链接：https://leetcode.cn/problems/binary-tree-pruning/

思路解析

剪枝问题通常采用后序遍历的思想：先处理子树，再决定当前节点是否保留。

1. 递归逻辑：先递归清理左右子树。
2. 判断依据：如果当前节点为 0，且左右子树均已被剪掉（为空），则当前节点也应被剪掉。
3. 返回值：返回处理后的当前节点指针。

代码实现

class Solution {
public:
    TreeNode* pruneTree(TreeNode* root) {
        if (!root) return nullptr;
        
        // 后序遍历：先处理子树
        root->left = pruneTree(root->left);
        root->right = pruneTree(root->right);
        
        // 如果当前节点为 0 且无子节点，剪除
        if (root->val == 0 && !root->left && !root->right) {
            return nullptr;
        }
        
        return root;
    }
};

四、验证二叉搜索树

题目链接：https://leetcode.cn/problems/validate-binary-search-tree/

思路解析

二叉搜索树（BST）的中序遍历结果应当是严格递增的序列。利用这一性质，我们可以通过中序遍历来验证。

1. 全局状态：使用一个变量记录前一个访问节点的值 prev。
2. 剪枝优化：一旦检测到不满足递增条件，立即返回 false，无需继续遍历。
3. 边界处理：空树视为有效 BST。

代码实现

class Solution {
    long prev = LONG_MIN; // 初始化前驱值为最小值
public:
    bool isValidBST(TreeNode* root) {
        if (!root) return true;
        
        // 递归左子树
        bool left = isValidBST(root->left);
        if (!left) return false; // 剪枝
        
        // 检查当前节点
        bool cur = (prev < root->val);
        prev = root->val;
        if (!cur) return false; // 剪枝
        
        // 递归右子树
        bool right = isValidBST(root->right);
        
        return left && right && cur;
    }
};

五、二叉搜索树中第 k 小的元素

题目链接：https://leetcode.cn/problems/kth-smallest-element-in-a-bst/description/

思路解析

同样利用 BST 中序遍历有序的特性。我们不需要遍历完整个树，只需找到第 k 个节点即可停止。

1. 计数器：维护一个 count 变量，初始化为 k。
2. 遍历顺序：左 -> 根 -> 右。
3. 提前终止：每访问一个节点，count--。当 count 变为 0 时，当前节点即为答案。

代码实现

class Solution {
    int count;
    int ret = 0;
    
    void dfs(TreeNode* root) {
        if (!root || count == 0) return;
        
        dfs(root->left);   // 先左
        count--;           // 访问根
        if (count == 0) ret = root->val;
        dfs(root->right);  // 后右
    }
    
public:
    int kthSmallest(TreeNode* root, int k) {
        count = k;
        dfs(root);
        return ret;
    }
};

复杂度分析

• 时间复杂度：最坏 O(N)，平均接近 O(k)。因为找到目标后可提前返回。
• 空间复杂度：O(H)，H 为树的高度，取决于递归栈的深度。

六、二叉树的所有路径

题目链接：https://leetcode.cn/problems/binary-tree-paths/

思路解析

这是回溯法的经典应用。我们需要记录从根到当前节点的路径字符串，并在到达叶子节点时保存结果。

1. 路径构造：每次向下递归，将当前节点值拼接到路径字符串后，并加上 ->。
2. 叶子节点：当左右子树均为空时，将完整路径加入结果集。
3. 回溯：虽然这里使用传值方式（string path），但逻辑上相当于回溯，确保每条路径独立。

代码实现

class Solution {
    vector<string> ret;
    
    void dfs(TreeNode* root, string path) {
        if (!root) return;
        
        // 拼接当前节点值
        path += to_string(root->val);
        
        // 如果是叶子节点，保存路径
        if (!root->left && !root->right) {
            ret.push_back(path);
            return;
        }
        
        // 非叶子节点，添加连接符并继续
        path += "->";
        dfs(root->left, path);
        dfs(root->right, path);
    }
    
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        string path;
        dfs(root, path);
        return ret;
    }
};

复杂度分析

• 时间复杂度：O(N * H)，N 为节点数，H 为树高。每个节点访问一次，字符串拼接成本与路径长度相关。
• 空间复杂度：O(H)，递归栈深度。

结语

深度优先搜索不仅是二叉树操作的基础，更是处理递归结构问题的通用策略。从简单的数值计算到复杂的路径回溯，理解 DFS 的核心思想——'深入探索，适时回退'，能帮助你应对更多算法挑战。希望这些实战案例能让你对递归有更直观的认识。