劍指offer之二叉搜索樹的第K個(gè)節(jié)點(diǎn)

1 問題

給定一顆二叉搜索樹，請找出其中的第k小的結(jié)點(diǎn)。例如， 5  3  7  2  4  6  8 中，按結(jié)點(diǎn)數(shù)值大小順序第三個(gè)結(jié)點(diǎn)的值為4。

 
2 分析

二叉樹定義：二叉查找樹（Binary Search Tree），（又：二叉搜索樹，二叉排序樹）它或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹： 若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值； 若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值； 它的左、右子樹也分別為二叉排序樹。

具體分析：按照定義，我們不難知道二叉查找樹如果按照數(shù)的中序遍歷，我們可以得到單調(diào)遞增的排列數(shù)，我們需要找到第K個(gè)節(jié)點(diǎn)，也就是中序遍歷樹的第K個(gè)節(jié)點(diǎn)。

我們可以通過遞歸中序遍歷求解答，也可以通過通過棧來實(shí)現(xiàn)樹的中序遍歷


 
3 代碼實(shí)現(xiàn)

    #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函數(shù)彈出來，不然永遠(yuǎn)都是二叉樹的最左下角的值
                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 運(yùn)行結(jié)果

    result is 4
    result1 is 4

 
5 總結(jié)

我們用棧(stack)進(jìn)行中序遍歷的時(shí)候，我們不應(yīng)該一開始就把樹的頂部節(jié)點(diǎn)壓入棧，這個(gè)時(shí)候基本上后面再在while循環(huán)里面做top操作基本上無解，然后我們既然是要執(zhí)行左 中 右效果，我們需要單獨(dú)定義一個(gè)遍歷保存第一個(gè)節(jié)點(diǎn)，然后依次壓入左孩子節(jié)點(diǎn)，然后如果是空就不壓進(jìn)去，而要執(zhí)行獲取頂部元素，這個(gè)就是我們需要的值，然后還有把這個(gè)元素進(jìn)行彈出來(pop)操作，然后把這個(gè)值的右孩子節(jié)點(diǎn)壓入棧，這樣就可以保證是左 中 右打印值的效果。




 


作者：chen.yu
深信服三年半工作經(jīng)驗(yàn)，目前就職游戲廠商，希望能和大家交流和學(xué)習(xí),
微信公眾號：編程入門到禿頭 或掃描下面二維碼
零基礎(chǔ)入門進(jìn)階人工智能(鏈接)