怎么跟客户介绍网站建设,中企动力潍坊分公司,部门网站建设管理办法,企业文化❓剑指 Offer 54. 二叉搜索树的第k大节点
难度#xff1a;简单
给定一棵二叉搜索树#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
输出…❓剑指 Offer 54. 二叉搜索树的第k大节点
难度简单
给定一棵二叉搜索树请找出其中第 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 ≤ 二叉搜索树元素个数
思路中序遍历
找第 k 大的结点二叉搜索树的中序遍历结果是从小到大排序:
所以其实就是对二叉搜索树进行 倒过来的中序遍历 遍历顺序为右 - 中 - 左每遍历一个元素 k--当 k 0 时就是最终结果。
代码(C、Java)
C
/*** 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 {
private:int ans 0;void inOrder(TreeNode* root, int k){if(root nullptr || k 0) return;inOrder(root-right, k);if(--k 0){ans root-val;return;}inOrder(root-left, k);}
public:int kthLargest(TreeNode* root, int k) {inOrder(root, k);return ans;}
};Java
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val x; }* }*/
class Solution {private int ans, k;private void inOrder(TreeNode root){if(root null || k 0) return;inOrder(root.right);if(--k 0){ans root.val;return;}inOrder(root.left);}public int kthLargest(TreeNode root, int k) {this.k k;inOrder(root);return ans;}
}运行结果 复杂度分析
时间复杂度 O ( n ) O(n) O(n)当树退化为链表时全部为右子节点无论 k 的值大小递归深度都为 n 占用 O ( n ) O(n) O(n) 时间。空间复杂度 O ( n ) O(n) O(n)当树退化为链表时全部为右子节点系统使用 O ( n ) O(n) O(n) 大小的栈空间。
题目来源力扣。 放弃一件事很容易每天能坚持一件事一定很酷一起每日一题吧 关注我LeetCode主页 / CSDN—力扣专栏每日更新 注 如有不足欢迎指正
