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

Question

我正在使用 Java 作为二叉树（不是二叉搜索树）。我有 class 和实例变量声明：

class intBTNode
{
     private int data;
     private intBTNode left;
     private intBTNode right;

我想做的是编写一个方法，仅当树中的所有条目都等于目标数或树为空时才 returns 为真。我写了下面的代码：

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

你应该更换

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;

与

return root.data == target && allEqual(root.left, target) && allEqual(root.right, target);

因为您当前的代码忽略了右子树（而且，空检查是多余的，因为您每次检查根是否为空）

至于避免递归，您可以使用不同的 while 循环，将当前节点的子节点压入堆栈（用根初始化）并始终弹出第一个元素。（当然，同时data == target）

Answer 2

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

问题是如果 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);
}

如果你出于某种原因想避免递归，你可以通过维护你已经"discovered"（通过访问它们的父节点）但实际上还没有 "visited"（通过检查它们的 data 和子节点），并不断从该集合中拉出节点，并访问它们，直到它为空：

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 作为堆栈而不是使用调用堆栈。）

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

Verifying all data entries in a binary tree are equal

java

algorithm

binary-tree