我试图找出该程序是否可以检查二叉树是否为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.MaxValue
和int.MinValue
。这样做至少有两个很好的理由:
int.MaxValue
和传递int.MinValue
,您要求左右子对象仅小于/大于其父对象,且没有其他边界。例如,您不必在乎第一个左孩子是否大于某个特定值,而不必小于根值!通过发送int.MinValue
来确保它始终大于该值,因此您只是在检查上限。本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句