深度优先的艺术：探索二叉树的深搜算法精髓

suye

发布于 2024-12-20 08:56:03

12500

代码可运行

文章被收录于专栏：17的博客分享17的博客分享

运行总次数：0

代码可运行

前言

二叉树作为一种重要的数据结构，在算法领域有着广泛的应用，而深度优先搜索（DFS）是二叉树遍历和操作的核心算法之一。通过 DFS，可以以递归或迭代的方式深入探索树的每一个节点，并高效地解决路径查找、节点计数、最大深度等问题。在这篇文章中，我们将深入剖析二叉树的深搜算法，从基础概念到典型应用，再到代码实现，带你全面掌握这一重要的算法工具。

☀️一、计算布尔二叉树的值

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

🌙解法

相同子问题：左孩子和右孩子进行父节点对应的运算——函数头bool evaluateTree(TreeNode* root)
对一个子问题进行分析：
- **先特判：**首先这是一个完整二叉树，如果根结点的左孩子为空，即代表右孩子也为空，则直接返回根节点对应的布尔值
- **函数体：**我们现在需要的是该结点左右孩子的布尔值，则直接调用evaluateTree(TreeNode* root->left)和evaluateTreel(TreeNode* root->right),无条件相信它一定能帮我们得到左右孩子的布尔值
- 根据父节点的值判断返回表达式的类型

我们结合示例分析：

⭐代码

/**
 * 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:
    bool evaluateTree(TreeNode* root) {
        if(!root->left) return root->val == 0? false: true;
        bool left = evaluateTree(root->left);
        bool right = evaluateTree(root->right);
        return root->val == 2? left | right: left & right;
    }
};

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

题目链接：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/

🌙解法

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

☁️步骤

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

如图分析：

⭐代码

/**
 * 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 时，当前节点即为目标值。

☁️步骤

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

🌀时间和空间复杂度分析

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

☀️六、二叉树的所有路径

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

🌙解法

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

☁️步骤

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

🌀时间复杂度分析

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

结语

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

今天的分享到这里就结束啦！如果觉得文章还不错的话，可以三连支持一下，17的主页还有很多有趣的文章，欢迎小伙伴们前去点评，您的支持就是17前进的动力！

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-12-09，如有侵权请联系 cloudcommunity@tencent.com 删除

遍历