[LeetCode] Kth Smallest Element in a BST

简介: This link suggests a concise C++ recursive solution. The original code may be hard to understand at first and I have rewritten the code below.

This link suggests a concise C++ recursive solution. The original code may be hard to understand at first and I have rewritten the code below. You may need to run some examples with it to see how it works.

 1 class Solution {
 2 public:
 3     int kthSmallest(TreeNode* root, int k) {
 4         return smallest(root, k);
 5     }
 6 private:
 7     int smallest(TreeNode* node, int& k) {
 8         if (!node) return -1;
 9         int val = smallest(node -> left, k);
10         if (!k) return val;
11         if (!--k) return node -> val;
12         return smallest(node -> right, k);
13     }
14 };

The same author also posts three solutions which is more space-efficient in this link.  All of them reduce the O(n) space of the above code to O(k) space by using some nice data structures.

Personally I really love the soltuion using deque and I have rewritten it below.

 1 class Solution {
 2 public:
 3     int kthSmallest(TreeNode* root, int k) {
 4         TreeNode* node = root;
 5         deque<TreeNode*> nodes;
 6         while (true) {
 7             while (node) {
 8                 nodes.push_front(node);
 9                 if (nodes.size() > k)
10                     nodes.pop_back();
11                 node = node -> left;
12             }
13             node = nodes.front();
14             nodes.pop_front();
15             if (!--k) return node -> val;
16             node = node -> right;
17         }
18     }
19 };

 

目录
相关文章
|
8月前
Leetcode 230. Kth Smallest Element in a BST
先来看下二叉搜索树的性质,对于任意一个非叶子节点,它的左子树中所有的值必定小于这个节点的val,右子树中所有的值必定大于或等于当前节点的val。 这条性质就保证了如果我们对二叉搜索树做中序遍历,中序遍历的结果肯定是有序的。对于此题而言,我们只需要拿到中序遍历结果,然后返回第k个即可,时间复杂度是O(n)。
51 1
|
Python
LeetCode 378. Kth S Element in a Sorted Matrix
给定一个 n x n 矩阵,其中每行和每列元素均按升序排序,找到矩阵中第k小的元素。 请注意,它是排序后的第k小元素,而不是第k个元素。
85 0
LeetCode 378. Kth S Element in a Sorted Matrix
|
算法
LeetCode 229. Majority Element II
给定一个大小为 n 的数组,找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。 说明: 要求算法的时间复杂度为 O(n),空间复杂度为 O(1)。
69 0
LeetCode 229. Majority Element II
|
算法 Python
LeetCode 169. 多数元素 Majority Element
LeetCode 169. 多数元素 Majority Element
LeetCode 215. Kth Largest Element in an Array
在未排序的数组中找到第 k 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。
66 0
|
1月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
1月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
1月前
|
索引
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
|
1月前
|
算法
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
|
1月前
|
算法 容器
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词