剑指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)操作，然后把这个值的右孩子节点压入栈，这样就可以保证是左 中 右打印值的效果。