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

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

Flutter 组件 random_color 的适配 鸿蒙Harmony 实战 - 驾驭视觉美学随机化、实现鸿蒙端高阶灵动 UI 调色盘与动态主题生成方案

Flutter 组件 random_color 的适配 鸿蒙Harmony 实战 - 驾驭视觉美学随机化、实现鸿蒙端高阶灵动 UI 调色盘与动态主题生成方案

欢迎加入开源鸿蒙跨平台社区：https://openharmonycrossplatform.ZEEKLOG.net Flutter 组件 random_color 的适配 鸿蒙Harmony 实战 - 驾驭视觉美学随机化、实现鸿蒙端高阶灵动 UI 调色盘与动态主题生成方案 前言 在鸿蒙（OpenHarmony）应用开发中，尤其是在涉及内容创作、个性化看板或动态标签系统时，我们经常需要生成一些“丰富多彩但又不显杂乱”的颜色。如果你仅仅依赖 Random().nextInt(0xFFFFFF)，那么生成的色彩极易出现灰暗、过度饱和或者是对比度极低的“色块灾难”。 一个具备极致审美的鸿蒙应用，应当学会在随机中寻找平衡。 random_color 是一套基于色彩理论的高阶生成引擎。它不仅能产生随机色，更能根据“色相（Hue）”、“明度（Luminosity）”和“饱和度”进行定向搜索。适配到鸿蒙平台后，它不仅能支撑起灵动的 UI

By Ne0inhk
鸿蒙APP开发从入门到精通：性能优化与Next原生合规

鸿蒙APP开发从入门到精通：性能优化与Next原生合规

《鸿蒙APP开发从入门到精通》第11篇：性能优化与Next原生合规 🏎️✅ 内容承接与核心价值 这是《鸿蒙APP开发从入门到精通》的第11篇——性能优化与Next原生合规篇，承接第10篇的「AI原生与用户增长」，100%复用项目架构，为后续第12篇的电商购物车全栈项目最终上线铺垫性能优化与Next原生合规的核心技术。 学习目标： * 掌握鸿蒙APP性能优化的定义与架构； * 实现启动优化、渲染优化、网络优化等性能优化功能； * 理解Next原生合规的原理与实现方式； * 开发代码规范、权限合规、数据合规等合规功能； * 优化性能与合规的用户体验（响应速度、内存占用、电池消耗）。 学习重点： * 鸿蒙APP性能优化的开发流程； * 性能优化的分类与使用场景； * 启动优化、渲染优化、网络优化的实现； * Next原生合规的设计与实现。 一、 性能优化基础 🎯 1.1 性能优化定义 性能优化是指对应用进行优化，提高应用的响应速度、降低内存占用、减少电池消耗等，主要包括以下方面： * 启动优化：优化应用的启动时间； * 渲染优化：优化应用的界

By Ne0inhk
《Linux复习指南》Shell脚本中最常见指令总结

《Linux复习指南》Shell脚本中最常见指令总结

每日激励：“不设限和自我肯定的心态：I can do all things。 — Stephen Curry” ———————— 早关注不迷路，话不多说安全带系好，发车啦（建议电脑观看）。 Linux常见指令总结 对于一些简单的就不过诉了（自己可以忘记的可以多尝试下） 1. 创建目录：mkdir <dir目录名> 可以递归多层创建 2. 删除目录：rmdir <dir目录名> 3. 打开目录：cd <dir目录名> 4. 删除文件的指令：rm -r：递归式删除，可以删除掉目录 -f：不需要确认，自动确认要删除（一般在删除目录的时候会进行询问） 5. 查看目录中的文件：ls <dir目录名&

By Ne0inhk
大模型本地部署神器：llama.cpp使用介绍

大模型本地部署神器：llama.cpp使用介绍

介绍llama.cpp 本节主要介绍什么是llama.cpp，以及llama.cpp、llama、ollama的区别。同时说明一下GGUF这种模型文件格式。 什么是llama.cpp llama.cpp是一个由Georgi Gerganov开发的高性能C++库，主要目标是在各种硬件上（本地和云端）以最少的设置和最先进的性能实现大型语言模型推理。 主要特点： * 纯C/C++实现，没有任何依赖 * 对Apple Silicon（如M1/M2/M3芯片）提供一流支持 - 通过ARM NEON、Accelerate和Metal框架优化 * 支持x86架构的AVX、AVX2、AVX512和AMX指令集 * 支持1.5位、2位、3位、4位、5位、6位和8位整数量化，实现更快的推理和更低的内存使用 * 为NVIDIA GPU提供自定义CUDA内核（通过HIP支持AMD GPU，通过MUSA支持摩尔线程MTT GPU）

By Ne0inhk