验证二叉树中所有的数据项都等于

我使用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; 
}

我想我的工作方式，通过这个来检查代码，但我不知道我充分检查所有节点（即叶）的。此外，我试图找出一种方法来攻击这个问题是不是递归或会更有效。任何帮助或建议，将不胜感激。

来源

2016-09-24 Dustin

你是不是充分检查所有节点。

的问题是，如果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和儿童），并不断拉结点出该集合，并探访他们，直到它是空的：

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

来源

2016-09-24 22:01:37 ruakh

此时应更换

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）

来源

2016-09-24 21:54:02 eavidan

验证二叉树中所有的数据项都等于

回答

相关问题