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

LeetCode LeetCode 树深度优先搜索二叉树二叉搜索树

发布时间 : 2000-01-10 02:03

字数:1.3k 阅读 :

评论:

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

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^4
0 <= 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