java - 验证二叉树中的所有数据条目是否相等

Question

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

我正在努力通过这个检查代码，但我不确定我是否充分检查了所有节点(即叶节点)。另外，我正在尝试找出一种方法来解决这个问题，这种方法不是递归的，或者会更有效。如有任何帮助或建议，我们将不胜感激。

Answer 1

您没有充分检查所有节点。

问题是如果 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 作为堆栈而不是使用调用堆栈。)