递归搜索二叉树的C＃

-1

荫试图Findout如果这个程序可以检查是否二叉树是BST与否，递归搜索二叉树的C＃

以下是代码：

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

这个解决办法，而这不会对我eather工作！

这是我试过的代码：

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

结果是假，而这应该是真实的。

来源

2015-11-13 Kob_24

那么当您在1节点树上运行该代码时会发生什么？你说你不认为它会起作用;但你有没有尝试过，看到会发生什么？ – Servy

@Servy是的，我做了bro，得到了错误 –

哪些节点验证正确，哪些在调试程序时验证错误，并查看每个节点的验证方式？ – Servy

您的解决方案的出发点错误：

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。至少有两个充分的理由这样做：

如果根节点不具有左右的孩子，你的做法会引起的NullReferenceException
通过传递int.MaxValue和int.MinValue，你从左边和右边的孩子需要只有小于/大于其父母，没有另一个分界线。例如，你不应该在乎第一个左边的孩子是否大于某个特定值，它只需要小于根值！通过发送int.MinValue，您可以确保它始终大于该值，因此您只需检查上限。

来源

2015-11-13 21:37:35

感谢兄弟，这是一个很好的答案:) –

@ Kob_24没问题，欢迎您！ –

是否有比这更好的解决方案？ –

递归搜索二叉树的C＃

回答

相关问题