230.二叉搜索树中第K小的元素
230.1 题目
给定一个二叉搜索树的根节点 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 <= 10^40 <= Node.val <= 10^4
进阶：
如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？
230.2 题解
中序遍历递归法
// 方法一：中序遍历递归法
// 使用中序遍历二叉搜索树，并将结果存储在列表中，最后返回列表中的第 k 个元素
static int KthSmallest1(TreeNode root, int k)
{
// 用于存储中序遍历结果的列表
List<int> inorderList = new List<int>();
// 调用中序遍历函数
InorderTraversal(root, inorderList);
// 返回列表中的第 k 个最小元素（k 从 1 开始计数）
return inorderList[k - 1];
}
// 中序遍历递归函数
static void InorderTraversal(TreeNode node, List<int> inorderList)
{
// 如果节点为空，返回
if (node == null) return;
// 遍历左子树
InorderTraversal(node.left, inorderList);
// 访问当前节点，将节点值添加到列表中
inorderList.Add(node.val);
// 遍历右子树
InorderTraversal(node.right, inorderList);
}
中序遍历迭代法
// 方法二：中序遍历迭代法
// 使用栈进行中序遍历，在遍历过程中找到第 k 个最小元素并返回
static int KthSmallest2(TreeNode root, int k)
{
// 用于存储节点的栈
Stack<TreeNode> stack = new Stack<TreeNode>();
// 无限循环，直到找到第 k 个最小元素
while (true)
{
// 将所有左子节点压入栈中
while (root != null)
{
stack.Push(root);
root = root.left;
}
// 弹出栈顶节点
root = stack.Pop();
// 每弹出一个节点，k 减 1
if (--k == 0) return root.val;
// 转向右子树
root = root.right;
}
}
230.3 代码
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
#region 题目
// 给定一个二叉搜索树的根节点 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 <= 104
// 0 <= Node.val <= 104
// 进阶：如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？
#endregion
#region 测试
// 示例 1
TreeNode root1 = new TreeNode(3)
{
left = new TreeNode(1)
{
right = new TreeNode(2)
},
right = new TreeNode(4)
};
int k1 = 1;
int result1 = KthSmallest1(root1, k1);
Console.WriteLine($"示例1 方法1 输出：{result1}");
int result1_2 = KthSmallest2(root1, k1);
Console.WriteLine($"示例1 方法2 输出：{result1_2}");
// 示例 2
TreeNode root2 = new TreeNode(5)
{
left = new TreeNode(3)
{
left = new TreeNode(2)
{
left = new TreeNode(1)
},
right = new TreeNode(4)
},
right = new TreeNode(6)
};
int k2 = 3;
int result2 = KthSmallest1(root2, k2);
Console.WriteLine($"示例2 方法1 输出：{result2}");
int result2_2 = KthSmallest2(root2, k2);
Console.WriteLine($"示例2 方法2 输出：{result2_2}");
#endregion
}
#region 答案
// 方法一：中序遍历递归法
// 使用中序遍历二叉搜索树，并将结果存储在列表中，最后返回列表中的第 k 个元素
static int KthSmallest1(TreeNode root, int k)
{
// 用于存储中序遍历结果的列表
List<int> inorderList = new List<int>();
// 调用中序遍历函数
InorderTraversal(root, inorderList);
// 返回列表中的第 k 个最小元素（k 从 1 开始计数）
return inorderList[k - 1];
}
// 中序遍历递归函数
static void InorderTraversal(TreeNode node, List<int> inorderList)
{
// 如果节点为空，返回
if (node == null) return;
// 遍历左子树
InorderTraversal(node.left, inorderList);
// 访问当前节点，将节点值添加到列表中
inorderList.Add(node.val);
// 遍历右子树
InorderTraversal(node.right, inorderList);
}
// 方法二：中序遍历迭代法
// 使用栈进行中序遍历，在遍历过程中找到第 k 个最小元素并返回
static int KthSmallest2(TreeNode root, int k)
{
// 用于存储节点的栈
Stack<TreeNode> stack = new Stack<TreeNode>();
// 无限循环，直到找到第 k 个最小元素
while (true)
{
// 将所有左子节点压入栈中
while (root != null)
{
stack.Push(root);
root = root.left;
}
// 弹出栈顶节点
root = stack.Pop();
// 每弹出一个节点，k 减 1
if (--k == 0) return root.val;
// 转向右子树
root = root.right;
}
}
#endregion
}
// 定义二叉树节点类
public class TreeNode
{
public int val; // 节点值
public TreeNode left; // 左子节点
public TreeNode right; // 右子节点
// 构造函数，初始化节点值和子节点
public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
{
this.val = val;
this.left = left;
this.right = right;
}
}
230.4 运行结果
示例1 方法1 输出：1
示例1 方法2 输出：1
示例2 方法1 输出：3
示例2 方法2 输出：3
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com
