问题是我需要编写一个函数来验证二叉树是否是有效的二叉搜索树
这是我的代码:
public static boolean betterValidBSTArray(TreeNode node) {
WrapInt lastData = null;
return validate(lastData, node);
}
private static boolean validate(WrapInt lastData, TreeNode node) {
if(node == null) return true;
if(!validate(lastData, node.getLeft())) return false;
if(lastData != null && node.getData() <= lastData.value) return false;
if(lastData == null) lastData = new WrapInt();
lastData.value = node.getData();
if(!validate(lastData, node.getRight())) return false;
return true;
}
class WrapInt { int value; }
问题是,这个算法不起作用。我设置了一些断点,并发现对于每个堆栈调用,在堆栈调用完成后将lastData分配给一个值后,前一个堆栈调用将以lastData = null继续,即使lastData对于前一个堆栈调用具有实际值。
感谢您的帮助。
最佳答案
要修复您的代码,您不应该执行 if(lastData == null) lastData = new WrapInt();
因为它将对新对象的引用仅分配给本地的方法调用参数每个堆栈调用的变量,并且您不应将 null
作为 lastData
传递,而是传递一个将在整个递归中使用的对象,仅更改其值
.
关于Java对象不能通过递归通过ref传递,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31531506/