题解 | #JZ62二叉搜索树的第k个结点#
题目链接
题目描述
给定一棵二叉搜索树，请找出其中的第k小的TreeNode结点。
考查知识点
- 二叉搜索树(bst)
- 树的遍历
- 二叉搜索树中序遍历的特殊性质
分析
1.首先我们给出二叉搜索数的定义:
如果一颗二叉树，满足如下条件
- 若其结点的左子树不空，且左子树上所有结点的值均不大于它的根结点的值。
- 若任意结点的右子树不空，则右子树上所有结点的值均不小于它的根结点的值。
则我们称这样的二叉数为二叉搜索树
如下图即为一颗二叉搜索树(以下统称为bst), 对于任意节点，其左子树的所有节点一定不大于该节点，其右子树的节点一定不小于该节点
2.树的遍历: 关于树的四种遍历方式我在JZ61这道题中已经介绍，这里不做赘述，这里给需要的读者附上那题的链接:
https://blog.nowcoder.net/n/50edaca0531e4693a2db6e0575143d72
3.二叉搜索树中序遍历的特殊性质
关于这个性质当结论背过即可，该性质为:bst中序遍历得到的序列即为将bst上所有节点按从小到大排序的序列，可以举个例子说明其正确性:
解法一:使用递归实现中序遍历，因为bst的中序遍历结果即为节点的值从小到大排序的结果，所以通过一个全局变量记录当前遍历至第k个即可
- 优点:代码简洁，实现简单
- 缺点:递归所耗费的时间和空间比迭代实现大得多，若是多二者要求比较苛刻时要慎重考虑
正确代码及注释如下
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
int index = 0;
TreeNode* ans = nullptr;
TreeNode* KthNode(TreeNode* pRoot, int k) {
if(!pRoot) return nullptr; //边界处理
KthNode(pRoot->left, k); //处理左子树
index ++ ;
if(index == k) ans = pRoot; //处理当前节点
KthNode(pRoot->right, k); //处理右子树
return ans; //返回结果
}
};方法二:通过迭代的方式实现中序遍历，依旧是使用一个变量记录遍历至第k个
- 优点:
占用时间，空间少，速度较递归实现快 - 缺点:代码复杂，实现难度比递归写法大
正确代码及注释如下
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
TreeNode* KthNode(TreeNode* pRoot, int k) {
if(!pRoot || k == 0) return nullptr; //空树与边界处理
int idx = 0;
stack<TreeNode*> stk; //用栈模拟中序遍历的递归与回溯过程
while (pRoot || stk.size()) {
while (pRoot) { //先遍历左子树
stk.push(pRoot);
pRoot = pRoot->left;
}
pRoot = stk.top();
stk.pop(); //模拟回溯
idx ++;
if(idx == k) return pRoot; //再遍历当前节点
pRoot = pRoot->right; //最后遍历右子树
}
return nullptr;
}
};
