我将 Java 用于二叉树(而不是二叉搜索树)。我有类和实例变量声明:
class intBTNode
{
private int data;
private intBTNode left;
private intBTNode right;
我想做的是编写一个方法,仅当树中的所有条目都等于目标数或树为空时才返回 true。 我写了下面的代码:
public static boolean allEqual(intBTNode root, int target)
{
if (root == null)
return true;
if (root.data == target && root.left != null)
return allEqual(root.left, target);
if (root.data == target && root.right != null)
return allEqual(root.right, target);
return false;
}
我正在努力通过这个检查代码,但我不确定我是否充分检查了所有节点(即叶节点)。另外,我正在尝试找出一种方法来解决这个问题,这种方法不是递归的,或者会更有效。如有任何帮助或建议,我们将不胜感激。
最佳答案
您没有充分检查所有节点。
问题是如果 root.left
是非空的,那么你永远不会检查 root.right
;所以像这样的树:
3
/ \
3 4
将被错误分类为仅包含目标。
更好的方法是这样写:
public static boolean allEqual(intBTNode root, int target)
{
return root == null
|| root.data == target
&& allEqual(root.left, target)
&& allEqual(root.right, target);
}
如果出于某种原因你想避免递归,你可以通过维护你“发现”(通过访问它们的父节点)但还没有真正“访问”(通过检查它们的 data
和 children),并不断从该集合中拉出节点,并访问它们,直到它为空:
public static boolean allEqual(intBTNode root, int target)
{
List<intBTNode> nodesToVisit = new ArrayList<intBTNode>();
nodesToVisit.add(root);
while (! nodesToVisit.isEmpty()) {
intBTNode node = nodesToVisit.remove(nodesToVisit.size() - 1);
if (node == null)
continue;
if (node.data != target)
return false;
nodesToVisit.add(node.left);
nodesToVisit.add(node.right);
}
return true;
}
(这实际上完全等同于递归版本,只是使用 ArrayList
作为堆栈而不是使用调用堆栈。)
关于java - 验证二叉树中的所有数据条目是否相等,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39681276/