C++算法
二叉树深度优先搜索（DFS）算法详解与实战
二叉树深度优先搜索（DFS）是遍历和操作树结构的核心算法。文章通过六个典型 LeetCode 例题，涵盖布尔二叉树求值、根到叶数字之和、树剪枝、BST 验证、第 K 小元素及所有路径问题。详细解析了递归逻辑、中序遍历性质及回溯技巧，提供了完整的 C++ 代码实现与复杂度分析，帮助读者掌握 DFS 在二叉树场景下的应用策略。
二叉树深度优先搜索（DFS）是遍历和操作树结构的核心算法。文章通过六个典型 LeetCode 例题，涵盖布尔二叉树求值、根到叶数字之和、树剪枝、BST 验证、第 K 小元素及所有路径问题。详细解析了递归逻辑、中序遍历性质及回溯技巧，提供了完整的 C++ 代码实现与复杂度分析，帮助读者掌握 DFS 在二叉树场景下的应用策略。
二叉树作为一种重要的数据结构，在算法领域有着广泛的应用，而深度优先搜索（DFS）是二叉树遍历和操作的核心算法之一。通过 DFS，可以以递归或迭代的方式深入探索树的每一个节点，并高效地解决路径查找、节点计数、最大深度等问题。在这篇文章中，我们将深入剖析二叉树的深搜算法，从基础概念到典型应用，再到代码实现，带你全面掌握这一重要的算法工具。
bool evaluateTree(TreeNode* root)evaluateTree(root->left) 和 evaluateTree(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;
}
};
如图所示：
/**
* 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);
}
};
通过决策树分析：
Node* dfs(root)
/**
* 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;
}
};
如图分析：
/**
* 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
}
};
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;
}
};
vector<string> ret 存储所有路径的结果。string path 存储当前路径的字符串。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);
}
};
ret 占用的空间为 O(N)。深度优先搜索不仅是二叉树操作的基础算法，更是一种处理递归结构问题的通用策略。通过对 DFS 的深入理解和实践，可以在许多复杂问题中找到高效的解决方案。从基础到应用，希望这篇文章帮助你更好地掌握 DFS 算法，并在未来的编程之路上将其灵活运用到各类数据结构和问题中。记住，算法的艺术在于实践，而实践则在于深度的探索！
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online