递归搜索二叉树C#

Kob_24

我试图找出该程序是否可以检查二叉树是否为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);    
    }

我认为我的代码中缺少一些东西,例如,我不认为此代码可以在具有一个根和只有两个节点的树上工作。你们可以帮我解决问题吗?

我也在stackoverflow上找到了这个解决方案

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();
    }

结果为False,而应为True。

米尔詹·米基奇

解决方案的起点出现错误:

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

而不是传递的root.Left.Value,并root.Right.Value在递归函数,发送int.MaxValueint.MinValue这样做至少有两个很好的理由:

  • 如果根节点没有左或右子节点,则您的方法将导致NullReferenceException
  • 通过int.MaxValue传递int.MinValue,您要求左右子对象仅小于/大于其父对象,且没有其他边界。例如,您不必在乎第一个左孩子是否大于某个特定值,而不必小于根值!通过发送int.MinValue来确保它始终大于该值,因此您只是在检查上限。

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章