网站模板安装教程,wordpress 分类 文章,p2p网站建设后期维护,汕头如何建设网站设计1. 题目
给定一棵二叉搜索树#xff0c;请找出其中第k大的节点。
示例 1:
输入: root [3,1,4,null,2], k 13/ \1 4\2
输出: 4示例 2:
输入: root [5,3,6,2,4,null,null,1], k 35/ \3 6/ \2 4/1
输出: 4限制#xff1a;
1 ≤ k ≤ 二叉搜索树元素个数来源#xf…1. 题目
给定一棵二叉搜索树请找出其中第k大的节点。
示例 1:
输入: root [3,1,4,null,2], k 13/ \1 4\2
输出: 4示例 2:
输入: root [5,3,6,2,4,null,null,1], k 35/ \3 6/ \2 4/1
输出: 4限制
1 ≤ k ≤ 二叉搜索树元素个数来源力扣LeetCode 链接https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
请参考二叉树遍历循环写法总结
2.1 循环解法
class Solution {
public:int kthLargest(TreeNode* root, int k) {//右根左降序遍历stackTreeNode* s;while(root || !s.empty()){while(root){s.push(root);root root-right;}root s.top();s.pop();k--;if(k0)return root-val;root root-left;}return -1;}
};2.2 递归解法
class Solution {bool found false;int ans;
public:int kthLargest(TreeNode* root, int k) {dfs(root,k);return ans;}void dfs(TreeNode* root, int k){if(!root || found)return;dfs(root-right,k);k--;if(k 0){found true;ans root-val;}dfs(root-left,k);}
};
