剑指offer之二叉搜索树的第K个节点
1 问题
给定一颗二叉搜索树,请找出其中的第k小的结点。例如, 5 3 7 2 4 6 8 中,按结点数值大小顺序第三个结点的值为4。
2 分析
二叉树定义:二叉查找树(Binary Search Tree),(又:二叉搜索树,二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉排序树。
具体分析:按照定义,我们不难知道二叉查找树如果按照数的中序遍历,我们可以得到单调递增的排列数,我们需要找到第K个节点,也就是中序遍历树的第K个节点。
我们可以通过递归中序遍历求解答,也可以通过通过栈来实现树的中序遍历
3 代码实现
#include <iostream>
#include <stdlib.h>
#include <stack>
using namespace std;
typedef struct Tree
{
int value;
struct Tree* left;
struct Tree* right;
} Tree;
Tree* getNode(Tree* node, int k)
{
if (k <= 0)
{
std::cout << "输入的k值不合法" << std::endl;
return NULL;
}
int count;
if (node == NULL)
return NULL;
getNode(node->left, k);
//std::cout << "value is " << node->value <<std::endl;
count++;
if (count == k)
{
return node;
}
getNode(node->right, k);
return node;
}
Tree* getNode1(Tree* node, int k)
{
if (k <= 0)
{
std::cout << "输入的k值不合法" << std::endl;
return NULL;
}
if (node == NULL)
return NULL;
std::stack<Tree *> stack;
Tree *p = node;
int count = 0;
while (p != NULL || !stack.empty())
{
if (p != NULL)
{
stack.push(p);
p = p->left;
}
else
{
Tree *value = stack.top();
//std::cout << "value is " << value->value << std::endl;
count++;
//这里需要pop函数弹出来,不然永远都是二叉树的最左下角的值
stack.pop();
if (k == count)
{
return value;
}
p = value->right;
}
}
return NULL;
}
int main() {
/***
4
2 6
1 3 5 7
**/
Tree *node1 , *node2 , *node3, *node4, *node5, *node6, *node7;
node1 = (Tree *)malloc(sizeof(Tree));
node2 = (Tree *)malloc(sizeof(Tree));
node3 = (Tree *)malloc(sizeof(Tree));
node4 = (Tree *)malloc(sizeof(Tree));
node5 = (Tree *)malloc(sizeof(Tree));
node6 = (Tree *)malloc(sizeof(Tree));
node7 = (Tree *)malloc(sizeof(Tree));
node1->value = 4;
node2->value = 2;
node3->value = 6;
node4->value = 1;
node5->value = 3;
node6->value = 5;
node7->value = 7;
node1->left = node2;
node1->right = node3;
node2->left = node4;
node2->right = node5;
node3->left = node6;
node3->right = node7;
node4->left = NULL;
node4->right = NULL;
node5->left = NULL;
node5->right = NULL;
node6->left = NULL;
node6->right = NULL;
node7->left = NULL;
node7->right = NULL;
Tree *result = getNode(node1, 4);
if (result != NULL)
{
std::cout << "result is " << result->value << std::endl;
}
Tree *result1 = getNode1(node1, 4);
if (result1 != NULL)
{
std::cout << "result1 is " << result1->value << std::endl;
}
return 0;
}
4 运行结果
result is 4
result1 is 4
5 总结
我们用栈(stack)进行中序遍历的时候,我们不应该一开始就把树的顶部节点压入栈,这个时候基本上后面再在while循环里面做top操作基本上无解,然后我们既然是要执行左 中 右效果,我们需要单独定义一个遍历保存第一个节点,然后依次压入左孩子节点,然后如果是空就不压进去,而要执行获取顶部元素,这个就是我们需要的值,然后还有把这个元素进行弹出来(pop)操作,然后把这个值的右孩子节点压入栈,这样就可以保证是左 中 右打印值的效果。
赞 (0)