剑指offer - 63二叉搜索树的第k个结点
程序员文章站
2022-07-10 20:15:00
...
题目描述
给定一棵二叉搜索树,请找出其中第k小的结点。例如,(5,3,7,2,4,6,8) 中,按结点数值大小顺序第三小结点的值为4。
思路如下:
二叉搜索树的中序遍历,就是从小到大遍历,找到第k个节点,就是第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;
//递归中序遍历 第k个节点,就是第k小的节点
TreeNode* inorder_recursion(TreeNode* root, int k){
if(root){
TreeNode* node = inorder_recursion(root->left, k);
if(node){
return node; //root的左子树找到了第k小的节点
}
if(++index == k){
return root; //root就是第k小的节点
}
node = inorder_recursion(root->right, k);
if(node){
return node; //root的右子树上找到了第k小的节点
}
}
return NULL; //当前root节点不是第k小的节点,其左右子树也没有第k小的节点
}
//非递归中序遍历
TreeNode* inorder_norecursion(TreeNode* root, int k){
stack<TreeNode*> nodestack;
TreeNode* node = root;
while(!nodestack.empty() || node){
if(node){
nodestack.push(node);
node = node->left;
}
else{
node = nodestack.top();
index++;
if(index == k){
return node;
}
nodestack.pop();
node = node->right;
}
}
return NULL;
}
TreeNode* KthNode(TreeNode* pRoot, int k)
{
//return inorder_recursion(pRoot, k);
return inorder_norecursion(pRoot, k);
}
};