Java使用递归返回布尔值true

Question

我试图看看我的二进制搜索树中是否包含一个值,并且我使用递归遍历树.问题是函数返回false作为调用堆栈上的最后一个值而不是true.

这是伪代码:

public boolean containsValue(Node node, Value v) {

   if (node.value.equals(v)) {
     return true;
   } 
   containsValue(node.left, v); // <- search left tree
   containsValue(node.right, v); // <- search right tree

   return false;
}

这总是返回false.

但是我不能这样做,因为第二个return语句是死代码:

 return containsValue(node.left, v);
 return containsValue(node.left, v);

那么我该如何解决这个问题呢？

Answer 1

这解决了当前的问题,但不是搜索二叉树的正确或有效的方法,因为它没有做出关于向左或向右看的决定,它只是笨拙地向左看,然后向右看.对此的正确答案就在这里.

如果左侧节点包含它,或者(||)右侧节点包含它,您希望返回true .

return containsValue(node.left, v) || containsValue(node.right, v);

请注意,如果左边包含它,它会短路并且不会向右看.

你甚至可以完成整个事情:

return node.value.equals(v) ||
       containsValue(node.left, v) ||
       containsValue(node.right, v);