二叉搜索树中第 k 小的元素与二叉树的所有路径算法解析
二叉搜索树中第 K 小元素的查找利用中序遍历特性,结合计数器剪枝优化,仅需遍历前 K 个节点即可找到目标值,避免全量遍历。二叉树所有路径的生成采用深度优先搜索(DFS)配合回溯策略,使用局部变量记录当前路径,在遇到叶子节点时将完整路径存入结果集,并在递归返回时恢复现场。代码实现基于 C++,展示了具体的类结构与递归逻辑,适用于理解递归、搜索与回溯算法在树结构中的应用。

二叉搜索树中第 K 小元素的查找利用中序遍历特性,结合计数器剪枝优化,仅需遍历前 K 个节点即可找到目标值,避免全量遍历。二叉树所有路径的生成采用深度优先搜索(DFS)配合回溯策略,使用局部变量记录当前路径,在遇到叶子节点时将完整路径存入结果集,并在递归返回时恢复现场。代码实现基于 C++,展示了具体的类结构与递归逻辑,适用于理解递归、搜索与回溯算法在树结构中的应用。



上述解法不仅使用大量额外空间存储数据,并且会将所有的结点都遍历一遍。但是,我们可以根据中序遍历的过程,只需扫描前 k 个结点即可。因此,我们可以创建一个全局的计数器 count,将其初始化为 k,每遍历一个节点就将 count--。直到某次递归的时候,count 的值等于 0,说明此时的结点就是我们要找的结果。
/**
* 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, ret = 0;
int kthSmallest(TreeNode* root, int k) {
count = k;
dfs(root);
return ret;
}
void dfs(TreeNode* root) {
if(root == nullptr || count == 0) {
return;
}
dfs(root->left);
if(--count == 0) {
ret = root->val;
return;
}
dfs(root->right);
}
};



使用深度优先遍历 (DFS) 求解。路径以字符串形式存储,从根节点开始遍历,每次遍历时将当前节点的值加入到路径中,如果该节点为叶子节点,将路径存储到结果中。否则,将 "->" 加入到路径中并递归遍历该节点的左右子树。
定义一个结果数组,进行递归。递归具体实现方法如下:
特别地,我们可以只使用一个字符串存储每个状态的字符串,在递归回溯的过程中,需要将路径中的当前节点移除,以回到上一个节点。
/**
* 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:
// 用全局变量 ret 记录所有路径,全局不会受到递归回溯的影响
vector<string> ret;
vector<string> binaryTreePaths(TreeNode* root) {
string path; // 用局部变量 path 记录路径的值,不用全局变量是为了便于回溯时'恢复原状'
dfs(root, path);
return ret;
}
void dfs(TreeNode* root, string path) {
// 递归的结束条件:当前结点为空则结束递归进行返回
if(root == nullptr) {
return;
}
// 当遇到叶子结点时则不用再添加箭头,并且此时一条路径已经结束,
// 用 string 数组 ret 进行记录并且直接返回
if(root->left == nullptr && root->right== nullptr) {
path += to_string(root->val);
ret.push_back(path);
return;
}
// 前序遍历
path += to_string(root->val);
path += "->";
dfs(root->left, path);
dfs(root->right, path);
}
};



微信公众号「极客日志」,在微信中扫描左侧二维码关注。展示文案:极客日志 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