递归搜索二叉树 C#

Question

我想看看这个程序是否可以检查二叉树是否是 BST，

代码如下：

public static bool isValidBST(Node root)
    {
        return isValid(root, root.Left.Value,
             root.Right.Value);
    }

    private static bool isValid(Node node, int MIN, int MAX)
    {
        // tree with no childres is BST
        if (node == null)
            return true;

        if (node.Value <= MIN || node.Value >= MAX)
            return false;

        return isValid(node.Left, MIN, node.Value) && isValid(node.Right, node.Value, MAX);    
    }

我认为我的代码中缺少一些东西，例如我认为这段代码不适用于只有一个根和两个节点的树。你们能帮我解决我的实现吗？

我也在 Whosebug

上找到了这个解决方案

private static bool isValid(Node node, int MIN, int MAX)
    {
        // tree with no childres is BST
        if (node == null)
            return true;

        if (node.Value > MIN && node.Value < MAX
            && isValid(node.Left, MIN, Math.Min(node.Value, MAX))
            && isValid(node.Right, Math.Max(node.Value, MIN), MAX))
            return true;
        else
            return false;
    }

但这对我天气不起作用！

这就是我尝试代码的方式：

 public static void Main(string[] args)
    {
        Node n1 = new Node(1, null, null);
        Node n3 = new Node(3, null, null);
        Node n2 = new Node(2, n1, n3);

        Console.WriteLine(isValidBST(n2));
        Console.ReadLine();
    }

结果为假，但应该为真。

Answer 1

你的解决方案起点有误：

public static bool isValidBST(Node root)
{
    return isValid(root, root.Left.Value,
        root.Right.Value);
}

不是在递归函数中传递 root.Left.Value 和 root.Right.Value，而是发送 int.MaxValue 和 int.MinValue。这样做至少有两个很好的理由：

如果根节点没有左或右 child，你的方法将导致 NullReferenceException
通过int.MaxValue和int.MinValue，你只需要从左边和右边child小于/大于它的parent，没有其他边界.例如，您不应该关心第一个左 child 是否大于某个特定值，它只需要小于根值即可！通过发送 int.MinValue，您可以确保它始终大于该值，因此您只是在检查上限。

递归搜索二叉树 C#

Recursive Search Binary Tree C#

c#

algorithm

binary-tree

binary-search-tree