博客网站模板下载,网站由哪几部分组成,四川省建设厅招标网站,邢台营销型网站建设文章目录概念查找二叉搜索树的第k大节点概念
二叉查找树#xff08;Binary Search Tree#xff09;#xff0c;#xff08;又名#xff1a;二叉搜索树#xff0c;二叉排序树#xff09;——它或者是一棵空树#xff0c;或者是具有下列性质的二叉树#xff1a;
若它的…
文章目录概念查找二叉搜索树的第k大节点概念
二叉查找树Binary Search Tree又名二叉搜索树二叉排序树——它或者是一棵空树或者是具有下列性质的二叉树
若它的左子树不空则左子树上所有结点的值均小于它的根结点的值若它的右子树不空则右子树上所有结点的值均大于它的根结点的值它的左、右子树也分别为二叉排序树。
二叉搜索树作为一种经典的数据结构它既有链表的快速插入与删除操作的特点又有数组快速查找的优势所以应用十分广泛例如在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作。
查找二叉搜索树的第k大节点 二叉搜索树如上如果我们想要返回其中第K大的节点应该怎么做呢
首先要知道一个性质二叉搜索树的中序遍历为 递增序列 。
给出的二叉搜索树中序遍历结果为 1, 2, 3, 4, 5, 6 因此想要获得第K大的节点只要倒序进行中序遍历左根右的顺序变为右根左即可得到降序排列的二叉搜索树节点序列序列中第K个元素即为我们所求。
代码实现
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {int res, k;void midsearch(TreeNode* root){if(rootnullptr) return;midsearch(root-right);if(k0) return;if(--k0) res root-val;midsearch(root-left);}
public:int kthLargest(TreeNode* root, int k) {this-k k;midsearch(root);return res;}
};
