一个方法应该一次只做一件事情。而且你所做的方式通常很奇怪。
我会给你一些类似Java的伪代码。对此我很抱歉,因为我已经有一段时间没有接触Java了。希望这可以帮到你。看看我在问题上的注释,希望你能解决它!
像这样调用你的isBST:
public boolean isBst(BNode node)
{
return isBinarySearchTree(node , Integer.MIN_VALUE , Integer.MIN_VALUE);
}
内部实现:
public boolean isBinarySearchTree(BNode node , int min , int max)
{
if(node.data < min || node.data > max)
return false;
boolean leftIsBst = false;
if(node.left != null)
{
if(node.left.data < node.data)
{
leftIsBst = isBinarySearchTree(node.left , min , node.data);
}else
{
leftIsBst = false;
}
}else
{
leftIsBst = true;
}
boolean rightIsBst = false;
if(node.right != null)
{
if(node.right.data >= node.data)
{
rightIsBst = isBinarySearchTree(node.right , node.data+1 , max);
}else
{
rightIsBst = false;
}
}else
{
rightIsBst = true;
}
return (leftIsBst && rightIsBst);
}
现在:如果你想要找到每个子树的最小值和最大值,你应该使用一个容器(我使用了一个ArrayList),并存储一个三元组,它表示根节点和相应的值(显然)。
例如:
class TreeValues
{
BNode root;
int Min;
int Max;
TreeValues(BNode _node , _min , _max)
{
root = _node;
Min = _min;
Max = _max;
}
}
并且:
ArrayList<TreeValues> myValues = new ArrayList<TreeValues>;
现在这是一种方法,用于查找给定节点的最小值
和最大值
:
public TreeValues GetSubTreeValues(BNode node)
{
BNode SubtreeRoot = node;
int MinValue = 0;
if(node.left == null)
{
MinValue = node.data;
}else
{
while(node.left != null)
{
node = node.left;
}
MinValue = node.data;
}
node = SubtreeRoot;
if(node.right == null)
{
MaxValue = node.data;
}else
{
int MaxValue = 0;
while(node.right != null)
{
node = node.right;
}
MaxValue = node.data;
}
return new TreeValues(SubtreeRoot , MinValue , MaxValue);
}
但是这只返回一个节点的值,所以我们将使用它来查找整个树:
public void GetTreeValues(BNode node)
{
myValues.add(GetSubTreeValues(node));
if(node.left != null)
GetTreeValues(node.left);
if(node.right != null)
GetTreeValues(node.right);
return;
}
使用这些方法,您的调用应该如下所示:
if(isBinarySearchTree(root))
GetTreeValues(root);
//else ... Do Something
这几乎是Java。只需要进行一些修改和修复就可以运行。找一本好的面向对象编程书籍,它会对你有所帮助。请注意,这个解决方案可以拆分成更多的方法。
{}
)来格式化您的代码以便更易于阅读。最后,您的代码有什么问题?我们到底在“检查”什么,您是否遇到错误? - LittleBobbyTables - Au Revoir