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

Ne0inhk

— 11 min read
深度优先的艺术：探索二叉树的深搜算法精髓
在这里插入图片描述

文章目录

前言

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

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

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

🌙解法

  1. 相同子问题：左孩子和右孩子进行父节点对应的运算——函数头bool evaluateTree(TreeNode* root)
  2. 对一个子问题进行分析：
    • **先特判：**首先这是一个完整二叉树，如果根结点的左孩子为空，即代表右孩子也为空，则直接返回根节点对应的布尔值
    • **函数体：**我们现在需要的是该结点左右孩子的布尔值，则直接调用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) {} * }; */classSolution{public:boolevaluateTree(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) {} * }; */classSolution{public:intdfs(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;}intsumNumbers(TreeNode* root){returndfs(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) {} * }; */classSolution{public: TreeNode*pruneTree(TreeNode* root){if(root ==nullptr)returnnullptr; 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) {} * }; */classSolution{long prev = LONG_MIN;// 定义并初始化全局变量prev，用于记录遍历过程中访问过的节点的最大值。public:boolisValidBST(TreeNode* root){if(!root)returntrue;// 如果当前节点为空（即已经遍历到叶子节点的下一个位置），则返回true。因为在二叉搜索树的定义中，空树被认为是有效的二叉搜索树。bool left =isValidBST(root->left);// 剪枝if(!left)returnfalse;bool cur =false;if(prev < root->val) cur =true; prev = root->val;// 剪枝if(!cur)returnfalse;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) {} * }; */classSolution{public:int count;int ret =0;voiddfs(TreeNode* root){if(!root || count ==0)return;dfs(root->left); count--;if(count ==0) ret = root->val;dfs(root->right);}intkthSmallest(TreeNode* root,int k){ count = k;dfs(root);return ret;}};

🌀时间和空间复杂度分析

  1. 时间复杂度：
    • 最坏情况下，需要访问所有节点，复杂度为 O ( N ) O(N) O(N)。
    • 平均情况下，可以在找到第 k 个元素时提前停止遍历，复杂度接近 O O O(k)。
  2. 空间复杂度：
    • 递归调用栈的空间复杂度为树的高度 O ( H ) O(H) O(H)。
    • 平衡二叉树的高度 H = l o g N H=logN H=logN；最坏情况下 H = N H=N 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) {} * }; */classSolution{public: vector<string> ret; vector<string>binaryTreePaths(TreeNode* root){ string path;dfs(root, path);return ret;}voiddfs(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 ) O(N) O(N)，其中 N N N 是节点总数。
    • 字符串拼接的复杂度为 O ( L ) O(L) O(L)，其中 L L L 是路径长度。由于二叉树的深度最大为 H H H ，总复杂度为 O ( N ⋅ H ) O(N⋅H) O(N⋅H) 。
  2. 空间复杂度：
    • 栈的递归深度为树的高度 H H H ，因此空间复杂度为 O ( H ) O(H) O(H) 。
    • 结果数组 ret 占用的空间为 O ( N ) O(N) O(N) 。

结语

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

在这里插入图片描述

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

在这里插入图片描述

Read more

五分钟入门控制算法：MPC（模型预测控制）算法

五分钟入门控制算法：MPC（模型预测控制）算法

什么是控制算法？         比如我现在的无人机悬浮在空中的某个位置，我想要让他以最短时间抬升悬浮到上方10m的位置，那我要具体如何去调整输入（如电流、油门、功率），以最好的性能（时间最短）来达到预期的目标呢？那就需要控制算法来求解，来调整这些输入。         控制算法（Control Algorithm）本质上是一套控制机械系统运作的“数学指挥指令”。它告诉机器（如无人机、恒温空调、机械臂）如何根据目前的状态，通过调整输入（如电流、油门、功率）来达到预期的目标。         不同的算法有不同的使用场景与特性，有些适用于动态系统，有些适用于静态。有些适用于低阶系统，有些适用于高阶系统。有些计算量小，有些计算量大。所以衍生出了很多种控制算法。         如何根据不同的场景选择合适的控制算法，创造更厉害的控制算法，调整控制算法的参数使得任务完成的效果更好；如何让实时波形图（如 rqt_plot）更加贴合跟踪曲线；如何对机械系统编写“保护逻辑” ；如何处理传感器噪声与延迟，用一些滤波算法（卡尔曼滤波）做更好的状态估计。如何增加前馈（

By Ne0inhk

黑马程序员java web学习笔记--后端进阶（二）SpringBoot原理

目录 1 配置优先级 2 Bean的管理 2.1 Bean的作用域 2.2 第三方Bean 3 SpringBoot原理 3.1 起步依赖 3.2 自动配置 3.2.1 实现方案 3.2.2 原理分析 3.2.3 自定义starter 1 配置优先级 SpringBoot项目当中支持的三类配置文件： * application.properties * application.yml ❤ * application.yaml 配置文件优先级排名（从高到低）：properties配置文件 > yml配置文件 > yaml配置文件 虽然springboot支持多种格式配置文件，但是在项目开发时，推荐统一使用一种格式的配置。

By Ne0inhk

快速部署指南：CV-UNet图像抠图WebUI搭建

快速部署指南：CV-UNet图像抠图WebUI搭建 你是否还在为一张证件照反复调整魔棒选区而头疼？是否因为电商主图要批量换背景，不得不熬夜修图到凌晨？有没有试过打开PyTorch代码、配置CUDA环境、下载模型权重，结果卡在ModuleNotFoundError: No module named 'torch'就再也没继续下去？ 别折腾了。今天这篇指南不讲原理、不配环境、不写代码——只做一件事：从镜像启动到完成第一张人像抠图，全程不超过90秒。 我们用的是由开发者“科哥”二次开发构建的 cv_unet_image-matting图像抠图 webui 镜像。它不是Demo，不是玩具，而是一个真正开箱即用、界面清爽、参数直观、结果可靠的生产级AI抠图工具。没有命令行黑框，没有报错日志，只有紫蓝渐变的界面、三秒出图的响应，和一张干净利落的透明背景人像。 本文就是为你写的——给没装过CUDA的运营、没写过Python的设计师、不想碰终端的剪辑师，一份真正能“照着点、就能用”的部署实录。

By Ne0inhk
Flutter for OpenHarmony: Flutter 三方库 cached_query 为鸿蒙应用打造高性能声明式数据缓存系统（前端缓存终极方案）

Flutter for OpenHarmony: Flutter 三方库 cached_query 为鸿蒙应用打造高性能声明式数据缓存系统（前端缓存终极方案）

欢迎加入开源鸿蒙跨平台社区：https://openharmonycrossplatform.ZEEKLOG.net 前言 在进行 OpenHarmony 应用开发时，网络请求的响应速度直接决定了用户体验（体验 UX）。如果用户每次切换页面都必须等待加载动画，应用会显得非常低级。我们不仅需要处理异步数据请求，更需要一套精密的机制来解决以下痛点： 1. 自动缓存：第二次访问时应瞬间展示历史数据。 2. 过期失效（Stale-while-revalidate）：在展示旧数据的同时，后台静默拉取新数据。 3. 无限滚动：简单地处理分页与数据追加内容逻辑。 cached_query 是一个类似于 Web 端 React Query 的 Dart 状态管理库。它专注于数据获取与同步，让你的鸿蒙应用具备顶级的数据缓存表现。 一、核心缓存驱动机制 cached_query 在内存与数据源之间建立了一层“智能感知”缓存。 数据过期/缺失 返回新数据 发射流

By Ne0inhk