如何在不导入外部模块的情况下用Haskell判断二叉搜索树？

首先来看你给出的原实现代码：

type BSTree a = BinaryTree a
data BinaryTree a = Null | Node (BinaryTree a) a (BinaryTree a) deriving Show
flattenTree :: BinaryTree a -> [a]
flattenTree tree = case tree of
    Null -> []
    Node left val right -> (flattenTree left) ++ [val] ++ (flattenTree right)
isBSTree :: (Ord a) => BinaryTree a -> Bool
isBSTree btree = case btree of
    Null -> False
    tree -> (flattenTree tree) == sort (flattenTree tree)

这个思路是可行的——利用二叉搜索树中序遍历结果严格递增的特性来判断，但确实存在两个小问题：一是依赖Data.List的sort函数，二是效率不算高（展平树需要O(n)时间，排序需要O(n log n)时间，整体复杂度为O(n log n)，还需要额外存储整个遍历列表）。

无需外部模块的优化实现 #

我们可以换一种更贴合二叉搜索树本质的思路：递归遍历树的同时，为每个节点传递它的合法取值范围（下界和上界）。每个节点的值必须大于左子树的所有值，同时小于右子树的所有值，通过这种范围约束来完成判断。

用Maybe来表示初始的上下界（根节点没有固定的上下限，所以用Nothing），具体实现如下：

type BSTree a = BinaryTree a
data BinaryTree a = Null | Node (BinaryTree a) a (BinaryTree a) deriving Show

isBSTree :: (Ord a) => BinaryTree a -> Bool
isBSTree = isBSTreeHelper Nothing Nothing

-- 辅助函数：传递当前节点的合法最小值和最大值
isBSTreeHelper :: (Ord a) => Maybe a -> Maybe a -> BinaryTree a -> Bool
isBSTreeHelper _ _ Null = True  -- 空树默认视为合法BST，若需调整为空树不合法，此处改为False即可
isBSTreeHelper minVal maxVal (Node left val right) =
    -- 检查当前值是否在合法范围内
    valGreaterThanMin && valLessThanMax &&
    -- 左子树所有节点必须小于当前值，因此左子树的上界设为当前val
    isBSTreeHelper minVal (Just val) left &&
    -- 右子树所有节点必须大于当前值，因此右子树的下界设为当前val
    isBSTreeHelper (Just val) maxVal right
    where
        valGreaterThanMin = case minVal of
            Nothing -> True
            Just m -> val > m  -- 若支持重复值，可改为 >=，按需调整BST定义
        valLessThanMax = case maxVal of
            Nothing -> True
            Just m -> val < m

实现说明 #

1. 核心逻辑：

   • 空节点Null默认返回True，如果你的业务场景中空树不算合法BST，直接修改此处返回值即可。
   • 非空节点先检查自身值是否在[minVal, maxVal]的开区间内（支持重复值的话，可将比较运算符改为>=和<=）。
   • 递归检查左子树时，将左子树的上界设为当前节点值；递归检查右子树时，将右子树的下界设为当前节点值，以此约束子树的取值范围。

2. 优势对比：

   • 完全不需要导入任何外部模块，仅依赖Haskell基础语法和类型系统。
   • 时间复杂度为O(n)（仅需遍历树一次），空间复杂度为O(h)（h为树的高度，平衡树场景下h≈log n，最坏情况为n），比原方法更高效。
   • 避免了额外的列表存储和排序操作，逻辑更贴近二叉搜索树的定义本质。

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