題目描述

給定一顆二叉搜索樹，請(qǐng)找出其中的第k大的結(jié)點(diǎn)。例如， 5 / \ 3 7 /\ /\ 2 4 6 8 中，按結(jié)點(diǎn)數(shù)值大小順序第三個(gè)結(jié)點(diǎn)的值為4。 思路：二叉搜索樹的中序遍歷是遞增的序列，使用循環(huán)的中序遍歷找到第k個(gè)節(jié)點(diǎn)就行了，對(duì)中序遍歷的循環(huán)版本沒理解，使用一個(gè)stack，找到最左邊的節(jié)點(diǎn)，所以初始化的時(shí)候首先初始化節(jié)點(diǎn)，stack要為空。計(jì)數(shù)的cnt要初始化為0。不清楚的話就一個(gè)節(jié)點(diǎn)的時(shí)候判斷一下，然后p = p->right，不需要判斷為空，因?yàn)闉榭盏脑?#xff0c;上面的循環(huán)不會(huì)進(jìn)入。 /* struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {} }; */ class Solution { public:TreeNode* KthNode(TreeNode* pRoot, int k){if(pRoot == nullptr){return nullptr;}stack<TreeNode*> s; //s.push(pRoot);TreeNode* p = pRoot;int cnt = 0;while(!s.empty() || p != nullptr){while(p != nullptr){s.push(p);p = p->left;}if(!s.empty()){p = s.top();s.pop(); ++cnt;if(cnt == k){return p;} p = p->right; }}return nullptr;} };

?

轉(zhuǎn)載于:https://www.cnblogs.com/dingxiaoqiang/p/8310982.html

總結(jié)

以上是生活随笔為你收集整理的61二叉搜索树的第k个结点的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。