咨询：用二叉搜索树（BST）查找整数数组最小值的步骤是否正确？

嘿，你的思路其实是完全可行的！不过咱们可以利用二叉搜索树（BST）的特性，让找最小值的步骤更高效，不用做全树遍历～

首先明确：先把数组元素插入BST，再查找最小值这个逻辑是没问题的，完全能得到正确结果。不过结合BST的核心特性，我们可以优化查找环节，避免不必要的遍历。

• 第一步：构建二叉搜索树
  按照BST的插入规则，把数组中的每个元素依次插入树中：

  • 若当前节点为空，直接把元素作为新节点；
  • 若元素小于当前节点值，递归/迭代插入左子树；
  • 若元素大于当前节点值，递归/迭代插入右子树；
  • （注意：如果数组有重复元素，提前确定处理规则即可，比如放到左/右子树，这不影响最终找最小值的结果）

• 第二步：查找BST的最小值
  利用BST的关键特性：最小值一定在树的最左侧节点（不管是不是叶子节点）。所以不需要遍历整个树，只需要从根节点开始，一直往左走，直到没有左子节点为止，当前节点的值就是最小值。

结合你给出的代码片段，这里补全完整的实现：

using System;

// 定义BST节点类
public class TreeNode
{
    public int Val { get; set; }
    public TreeNode Left { get; set; }
    public TreeNode Right { get; set; }

    public TreeNode(int val)
    {
        Val = val;
        Left = null;
        Right = null;
    }
}

public class BstMinFinder
{
    // 插入节点到BST
    private static TreeNode Insert(TreeNode root, int val)
    {
        if (root == null)
        {
            return new TreeNode(val);
        }

        if (val < root.Val)
        {
            root.Left = Insert(root.Left, val);
        }
        else
        {
            // 重复值默认放到右子树，不影响最小值查找
            root.Right = Insert(root.Right, val);
        }

        return root;
    }

    // 查找BST的最小值
    private static int FindMin(TreeNode root)
    {
        if (root == null)
        {
            throw new InvalidOperationException("BST不能为空");
        }

        // 一直向左遍历，直到无左子节点
        while (root.Left != null)
        {
            root = root.Left;
        }

        return root.Val;
    }

    public static void Main()
    {
        int[] nums = { 5, 3, 7, 2, 4, 1, 6 };
        TreeNode root = null;

        // 构建BST
        foreach (int num in nums)
        {
            root = Insert(root, num);
        }

        // 查找并输出最小值
        int minVal = FindMin(root);
        Console.WriteLine($"数组的最小值是：{minVal}"); // 输出结果为1
    }
}

如果你的需求只是单纯找数组的最小值，其实直接遍历数组或者用C# Linq的nums.Min()方法效率更高，时间复杂度是O(n)；而构建BST的时间复杂度平均是O(n log n)，最坏情况（数组完全有序）是O(n²)。但如果是必须用BST来实现，那你的思路完全正确，而且我们优化后的查找步骤时间复杂度是O(h)（h为树的高度），比全树遍历更高效。

内容的提问来源于stack exchange，提问作者kurt