题目地址：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/
给定一棵二叉搜索树，请找出其中第k大的节点。
示例 1:
输入: root = [3,1,4,null,2], k = 1
3
/ \
1 4
\
2
输出: 4
示例 2:
输入: root = [5,3,6,2,4,null,null,1], k = 3
5
/ \
3 6
/ \
2 4
/
1
输出: 4
分析题目我们可以发现，二叉搜索树的中序遍历(左子树、根节点、右子树)为单调递增的序列，求二叉搜索树的第k大节点，等同于求二叉搜索树中序遍历的倒序的第k个节点，而二叉搜索树的倒序遍历(右子树、根节点、左子树)为单调递减序列。因为题目已知的是二叉搜索树，所以默认是已经排好序的，如果要求二叉树的第k大节点？那么如何做呢，通常的做法是利用二叉树中序遍历的有序性，将遍历的值存储在数组中，然后输出倒数第k个元素。当然，还有另一种经典方法就是使用优先队列实现大顶堆和小顶堆的方法。
优先队列默认是大顶堆，符合题目要求，所以我们通过深度优先搜索方法，将树中所有的节点的值加入优先队列（默认大顶堆）中，然后弹出优先队列中前k-1个元素，最后，队首元素即为所求值。
递归
/** * 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 { public: int cnt = 0; int res_num = 0; int kthLargest(TreeNode* root, int k) { dfs(root,k); return res_num; } void dfs(TreeNode* root, int k) { if(root == nullptr) return ; dfs(root->right, k); cnt++; if(cnt == k) res_num = root->val; dfs(root->left, 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 { public: int cnt = 0; //维护一个计数器 int kthLargest(TreeNode* root, int k) { if(root == nullptr) return 0; TreeNode* p = root; stack<TreeNode*> s; s.push(p); while(p || !s.empty()) { while(p) { s.push(p); p = p->right; } p = s.top(); s.pop(); cnt++; if(cnt == k) return p->val; p = p->left; } return 0; } };
大顶堆(优先队列)
/** * 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 { public: priority_queue<int> prior_que; void dfs(TreeNode* root) { prior_que.push(root->val); if(root->left != nullptr) dfs(root->left); if(root->right != nullptr) dfs(root->right); } int kthLargest(TreeNode* root, int k) { dfs(root); while(--k) { prior_que.pop(); } return prior_que.top(); };
二叉树求倒数第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 { public: int kthLargest(TreeNode* root, int k) { vector<int> res; stack<TreeNode*> s; TreeNode* p; p = root; while(p!=NULL || !s.empty()) { while(p != NULL) { s.push(p); p=p->left; } if(!s.empty()) { p = s.top(); s.pop(); res.push_back(p->val); p = p->right; } } return res[res.size() - k]; } };
原文：https://www.cnblogs.com/wzw0625/p/12677838.html