( “树” 之 BST) 230. 二叉搜索树中第K小的元素 ——【Leetcode每日一题】

二叉查找树（BST）：根节点大于等于左子树所有节点，小于等于右子树所有节点。
二叉查找树中序遍历有序。

230. 二叉搜索树中第K小的元素

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。

示例 1：

输入：root = [3,1,4,null,2], k = 1
输出：1

示例 2：

输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3

提示：

• 树中的节点数为 n 。
• 1 < = k < = n < = 1 0 4 1 <= k <= n <= 10^4 1<=k<=n<=104
• 0 < = N o d e . v a l < = 1 0 4 0 <= Node.val <= 10^4 0<=Node.val<=104

进阶： 如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？

思路：（中序遍历）

二叉搜索树中序遍历就是有序的，所以中序遍历该树，第k个节点的val即为第K小的元素。

法一：递归、法二：迭代

具体思路请看：94. 二叉树的中序遍历

代码：(Java、C++)

法一：递归
Java

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {private int cnt = 0;private int ans;public int kthSmallest(TreeNode root, int k) {cnt = k;dfs(root);return ans;}public void dfs(TreeNode root){if(root == null) return;dfs(root.left);if(--cnt == 0) {ans = root.val;return;}dfs(root.right);}
}

C++

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int cnt = 0;int ans;int kthSmallest(TreeNode* root, int k) {cnt = k;dfs(root);return ans;}void dfs(TreeNode* root){if(root == nullptr) return;dfs(root->left);if(--cnt == 0){ans = root->val;return;}dfs(root->right);}
};

法二：迭代
Java

class Solution {public int kthSmallest(TreeNode root, int k) {Stack<TreeNode> stk = new Stack<>();while(root != null || !stk.isEmpty()){while(root != null){stk.push(root);root = root.left;}root = stk.pop();if(--k == 0){return root.val;}root = root.right;}return 0;}
}

C++

class Solution {
public:int kthSmallest(TreeNode* root, int k) {stack<TreeNode*> stk;while(root != nullptr || !stk.empty()){while(root != nullptr){stk.push(root);root = root->left;}root = stk.top();stk.pop();if(--k == 0){return root->val;}root = root->right;}return 0;}
};

运行结果：

复杂度分析：

• 时间复杂度：$O(n)$，其中 n 是二叉树的节点数。最坏的情况下为k=n每一个节点恰好被遍历一次。
• 空间复杂度：$O(n)$，为递归或迭代过程中栈的开销，平均情况下为 $O(logn)$，最坏情况下树呈现链状，为 $O(n)$。

题目来源：力扣。

放弃一件事很容易，每天能坚持一件事一定很酷，一起每日一题吧！
关注我 leetCode专栏，每日更新！

注： 如有不足，欢迎指正！