专门制作网站,站内关键词排名软件,wordpress 图片并排,科技公司 网站设计经典案例题目描述 给定一颗二叉搜索树#xff0c;请找出其中的第k大的结点。例如#xff0c; 5 / \ 3 7 /\ /\ 2 4 6 8 中#xff0c;按结点数值大小顺序第三个结点的值为4。思路#xff1a;二叉搜索树的中序遍历是递增的序列#xff0c;使用循环的中序遍历找到第k个节点就行了请找出其中的第k大的结点。例如 5 / \ 3 7 /\ /\ 2 4 6 8 中按结点数值大小顺序第三个结点的值为4。 思路二叉搜索树的中序遍历是递增的序列使用循环的中序遍历找到第k个节点就行了对中序遍历的循环版本没理解使用一个stack找到最左边的节点所以初始化的时候首先初始化节点stack要为空。计数的cnt要初始化为0。不清楚的话就一个节点的时候判断一下然后p p-right不需要判断为空因为为空的话上面的循环不会进入。 /*
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;}stackTreeNode* 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;}
}; 转载于:https://www.cnblogs.com/dingxiaoqiang/p/8310982.html
