algorithm - 在二叉树中,查找值是否包含的算法

  显示原文与译文双语对照的内容
125 2

我有一个类 TreeNode,如下所示:

class TreeNode {
 int value;
 TreeNode left;
 TreeNode right;
public TreeNode(int x) {
 value = x;
}

如果 ( int i )的值为 node,那么我想写一个递归方法,其中包含的值,而 false 则为。

从我的理解,一个二进制树不必排序,所以我不应该比较当前 node的值。因此,我编写了以下方法:

public boolean contains(int i) {
 if (value == x) {
 return true;
 } else {
 if (left!= null) {
 return left.find(i);
 }
 if (right!= null) {
 return right.find(i);
 }
 }
 return false;
}

在这之后的思想是检查当前 node 值是否等于搜索值,如果不是 null,则递归调用左和右节点,否则方法将被递归调用。

如果搜索树左侧的一个值,这个方法最终返回 true,但是一旦我们搜索超出这个树的值的值,那么它将会被 return false 返回。我一直在选择我的大脑,我相信有一个相对较小的解决方案,但我看不到它。

时间:原作者:0个回答

142 5

像这样:

public boolean contains(int i) {
 return value == i ||
 left!= null && left.contains(i) ||
 right!= null && right.contains(i);
}
原作者:
109 5

如果返回递归调用的结果是 true 或者 false,则返回递归调用的结果是不正确的。

如果左子树搜索返回 false,则仍应搜索右子树。

public boolean contains(int i) {
 if (value == x) {
 return true;
 } else {
 boolean found = false;
 if (left!= null) {
 found = left.find(i);
 }
 if (!found && right!= null) {
 found right.find(i);
 }
 return found;
 }
}
原作者:
103 5

这似乎更正确:

public boolean contains(int i) {
 if (value == x) {
 return true;
 } else {
 if (left!= null && left.find(i)) {
 return true;
 }
 if (right!= null && right.find(i)) {
 return true;
 }
 }
 return false;
}
原作者:
84 4
 if (left!= null) {
 return left.find(i);
 }

这是问题。如果左边和右边都有 node,代码将只返回左边是否发现了任何内容。

相反,你需要的是:

 boolean found = false;
 if (left!= null) {
 found = left.find(i);
 }
 if (!found && right!= null) {
 found = right.find(i);
 }
 return found;
原作者:
77 0

实现首选左侧子树;它不在两个子树中正确搜索。可以按如下方式修复。

public boolean contains(int i) {
 boolean Result = value == x;
 if (left!= null) {
 Result |= left.find(i);
 }
 if (right!= null) {
 Result |= right.find(i);
 }
 return Result;
}

这里实现可以进一步优化,以便尽早返回。

public boolean contains(int i) {
 boolean Result = value == x;
 if (!Result && left!= null) {
 Result |= left.find(i);
 }
 if (!Result && right!= null) {
 Result |= right.find(i);
 }
 return Result;
}
原作者:
63 5

由于 TreeNode 类没有 find(int i) 方法,所以你的代码似乎没有 complile 。

我认为 contains() 方法应该看起来更像:

public boolean contains(TreeNode node, int i) {
 boolean result = node.value == i;
 if (left!= null) result |= contains(node.left, i);
 if (right!= null) result |= contains(node.right, i);
 return result;
}

当然,在方法的beggining中添加附加递归底部时,可以终止一个值并跳过两个 != null 检查:

public boolean contains(TreeNode node, int i) {
 if (node == null) return false;
 if (node.value == i) return true;
 return contains(node.left, i) || contains(node.right, i);
}

可以将它的进一步简化为一个衬垫:

public boolean contains(TreeNode node, int i) {
 return node!= null && 
 (node.value == i || contains(node.left, i) || contains(node.right, i));
}
原作者:
136 5

但是,我宁愿创建第二个具有参数TreeNode和int参数的static 方法,方法的正确修复如下所示:

public boolean contains(int i) {
 if (value == x) {
 return true;
 }
 if (left!= null && left.find(i)) {
 return true;
 }
 if (right!= null && right.find(i)) {
 return true;
 }
 return false;
}

代码中的错误是,如果左子树不包含值,则不会给出右子树的机会。如果不确定是否有任何其他结果,请不要返回值。

原作者:
...