劍指offer之二叉搜索樹(shù)的第K個(gè)節(jié)點(diǎn)
1 問(wèn)題
給定一顆二叉搜索樹(shù),請(qǐng)找出其中的第k小的結(jié)點(diǎn)。例如, 5 3 7 2 4 6 8 中,按結(jié)點(diǎn)數(shù)值大小順序第三個(gè)結(jié)點(diǎn)的值為4。
2 分析
二叉樹(shù)定義:二叉查找樹(shù)(Binary Search Tree),(又:二叉搜索樹(shù),二叉排序樹(shù))它或者是一棵空樹(shù),或者是具有下列性質(zhì)的二叉樹(shù): 若它的左子樹(shù)不空,則左子樹(shù)上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值; 若它的右子樹(shù)不空,則右子樹(shù)上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值; 它的左、右子樹(shù)也分別為二叉排序樹(shù)。
具體分析:按照定義,我們不難知道二叉查找樹(shù)如果按照數(shù)的中序遍歷,我們可以得到單調(diào)遞增的排列數(shù),我們需要找到第K個(gè)節(jié)點(diǎn),也就是中序遍歷樹(shù)的第K個(gè)節(jié)點(diǎn)。
我們可以通過(guò)遞歸中序遍歷求解答,也可以通過(guò)通過(guò)棧來(lái)實(shí)現(xiàn)樹(shù)的中序遍歷
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ù)彈出來(lái),不然永遠(yuǎn)都是二叉樹(shù)的最左下角的值
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)該一開(kāi)始就把樹(shù)的頂部節(jié)點(diǎn)壓入棧,這個(gè)時(shí)候基本上后面再在while循環(huán)里面做top操作基本上無(wú)解,然后我們既然是要執(zhí)行左 中 右效果,我們需要單獨(dú)定義一個(gè)遍歷保存第一個(gè)節(jié)點(diǎn),然后依次壓入左孩子節(jié)點(diǎn),然后如果是空就不壓進(jìn)去,而要執(zhí)行獲取頂部元素,這個(gè)就是我們需要的值,然后還有把這個(gè)元素進(jìn)行彈出來(lái)(pop)操作,然后把這個(gè)值的右孩子節(jié)點(diǎn)壓入棧,這樣就可以保證是左 中 右打印值的效果。
作者:chen.yu
深信服三年半工作經(jīng)驗(yàn),目前就職游戲廠商,希望能和大家交流和學(xué)習(xí),
微信公眾號(hào):編程入門(mén)到禿頭 或掃描下面二維碼
零基礎(chǔ)入門(mén)進(jìn)階人工智能(鏈接)