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

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

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

解法

如图所示：

• 我们以 5 这个点作为示例分析
• 值得注意的是递归的返回条件是当结点是叶子结点时，需要返回相加后的值，也就是在第一步之后检测

代码

/**
 * 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:
    int dfs(TreeNode* root, int prenum) {
        // 1.接收父节点的值并加上自己
        int nownum = prenum * 10 + root->val;
        // 2.检测叶子结点，设置递归终止条件
        if (root->left == nullptr && root->right == nullptr) return nownum;
        // 3.传值给左右孩子
        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/

解法

通过决策树分析：

• 以箭头所指结点分析，我需要左右子树的返回值判断自身的返回值，故此得到函数头——Node* dfs(root)
• 函数体总共有三点：
  1. 得到左子树的返回值
  2. 得到右子树的返回值
  3. 判断左右子树的返回值和自己的值并进行返回
• 递归出口：结点为空就返回空

代码

/**
 * 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:
    TreeNode* pruneTree(TreeNode* root) {
        if (root == nullptr) return nullptr;
        root->left = pruneTree(root->left);
        root->right = pruneTree(root->right);
        if (root->left == nullptr && root->right == nullptr && root->val == 0) root = nullptr;
        return root;
    }
};

四、验证二叉搜索树

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

解法

• 全局变量的优势
• 二叉搜索树的中序遍历结果就是一个有序数组
• 回溯与剪枝，通过剪枝来缩短编译时间

步骤

1. 左子树是二叉搜索树
2. 判断当前节点是否满足二叉搜索树的定义
3. 右子树是二叉搜索树

如图分析：

代码

/**
 * 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 {
    long prev = LONG_MIN; // 定义并初始化全局变量 prev，用于记录遍历过程中访问过的节点的最大值。
public:
    bool isValidBST(TreeNode* root) {
        if (!root) return true; // 如果当前节点为空（即已经遍历到叶子节点的下一个位置），则返回 true。因为在二叉搜索树的定义中，空树被认为是有效的二叉搜索树。
        bool left = isValidBST(root->left); // 剪枝
        if (!left) return false;
        bool cur = false;
        if (prev < root->val) cur = true;
        prev = root->val; // 剪枝
        if (!cur) return false;
        bool right = isValidBST(root->right);
        return left && right && cur; // 如果左子树、右子树以及当前节点都满足二叉搜索树的条件，则返回 true，表示整个树是有效的二叉搜索树。
    }
};

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

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

解法

• 利用中序遍历性质：
  • 中序遍历的顺序是：左子树 → 根节点 → 右子树。
  • 二叉搜索树的中序遍历会生成一个从小到大的排序序列，因此可以通过遍历的顺序找到第 k 个节点。
• 递归实现中序遍历：
  • 递归函数访问左子树时优先考虑小值。
  • 通过计数器 count 记录需要跳过的节点数，当 count == 0 时，当前节点即为目标值。

步骤

1. 初始化变量：
   • count 用于记录剩余需要遍历的节点数，初始值为 k。
   • ret 存储最终找到的第 k 小元素。
2. 定义递归函数 dfs：
   • 如果当前节点为空（root == NULL），直接返回。
   • 优先递归访问左子树：dfs(root->left)。
   • 每访问一个节点时，递减计数器：count--。
   • 检查是否找到目标元素（count == 0），如果是，将当前节点值存入 ret。
   • 然后递归访问右子树：dfs(root->right)。
3. 调用递归函数：
   • 在 kthSmallest 方法中，设置 count = k，然后调用 dfs(root) 开始中序遍历。
   • 遍历结束后，ret 中存储的就是第 k 小的元素。
4. 返回结果：
   • 返回 ret，即目标值。

如图分析：

代码

/**
 * 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:
    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);
    }
    int kthSmallest(TreeNode* root, int k) {
        count = k;
        dfs(root);
        return ret;
    }
};

时间和空间复杂度分析

1. 时间复杂度：
   • 最坏情况下，需要访问所有节点，复杂度为 O(N)。
   • 平均情况下，可以在找到第 k 个元素时提前停止遍历，复杂度接近 O(k)。
2. 空间复杂度：
   • 递归调用栈的空间复杂度为树的高度 O(H)。
   • 平衡二叉树的高度 H = logN；最坏情况下 H = N（退化为链表）。

六、二叉树的所有路径

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

解法

1. 二叉树的性质：
   • 每条路径可以通过深度优先搜索（DFS）遍历二叉树来构造。
   • 根节点到叶子节点的路径是每次遍历到叶子节点时的完整路径。
2. 实现方法：
   • 使用递归（DFS）逐层遍历节点，并构造当前路径。
   • 在叶子节点处，将路径加入结果集。

步骤

1. 定义数据结构与初始化：
   • 定义 vector<string> ret 存储所有路径的结果。
   • 定义 string path 存储当前路径的字符串。
2. 递归的逻辑（DFS）：
   • 如果当前节点为空，直接返回。
   • 如果当前节点是叶子节点（左右子树都为空）：
     • 将当前节点值拼接到路径字符串中。
     • 把路径字符串加入到结果集 ret 中。
   • 如果当前节点不是叶子节点：
     • 将当前节点值拼接到路径字符串中，并在后面加上 "->" 表示继续延续路径。
     • 递归遍历左子树和右子树，将更新后的路径传递下去。
3. 返回结果：
   • 递归完成后，返回结果数组 ret。

如图分析：

代码

/**
 * 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) return;
        if (!root->left && !root->right) {
            path += to_string(root->val);
            ret.push_back(path);
            return;
        } else {
            path += to_string(root->val) + "->";
            dfs(root->left, path);
            dfs(root->right, path);
        }
    }
};

时间复杂度分析

1. 时间复杂度：
   • 每个节点被访问一次，复杂度为 O(N)，其中 N 是节点总数。
   • 字符串拼接的复杂度为 O(L)，其中 L 是路径长度。由于二叉树的深度最大为 H，总复杂度为 O(N·H)。
2. 空间复杂度：
   • 栈的递归深度为树的高度 H，因此空间复杂度为 O(H)。
   • 结果数组 ret 占用的空间为 O(N)。

结语

深度优先搜索不仅是二叉树操作的基础算法，更是一种处理递归结构问题的通用策略。通过对 DFS 的深入理解和实践，可以在许多复杂问题中找到高效的解决方案。从基础到应用，希望这篇文章帮助你更好地掌握 DFS 算法，并在未来的编程之路上将其灵活运用到各类数据结构和问题中。算法的艺术在于实践，而实践则在于深度的探索！