java - 递归搜索二叉树问题

Question

我编写了以下代码用于递归搜索二叉树。即使我的 system.out 语句正在执行，return 语句也没有从整个递归中返回，因此这个方法没有返回 true。

谁能建议我如何从整个递归中返回。？

public static boolean isElementinTree(int num, BinaryTreeNode root) 
{
    if (root != null)
    {
        int rootVal = root.getData();
        BinaryTreeNode left = root.getLeft();
        BinaryTreeNode right = root.getRight();
        if (left != null)
        {
            isElementinTree(num,left);

        }
        if (right != null)
        {
            isElementinTree(num,right);
        }
        if (num == rootVal)
        {
            System.out.println("------ MATCH -----");               
            return true;
        }           
    }   
    return false;
}

score 11 · Accepted Answer

这就是问题：

if (left != null)
{
    isElementinTree(num,left);

}
if (right != null)
{
    isElementinTree(num,right);
}

在这些情况下，您正在调用该方法 - 但忽略了结果。我怀疑您只想更改其中的每一个以在发现时立即返回：

if (left != null && isElementinTree(num, left))
{
    return true;
}
if (right != null && isElementinTree(num, right))
{
    return true;
}

或者为了使整个事情更具声明性，您可以更简单地做到这一点：

public static boolean isElementinTree(int num, BinaryTreeNode root) 
{
    return root != null && (root.getData() == num ||
                            isElementInTree(num, root.getLeft()) ||
                            isElementInTree(num, root.getRight()));
}

可以使用 null 第二个参数进行调用isElementInTree，因为您已经在第一部分中防止了这种情况。

score 1 · Accepted Answer

像这样的简单解决方案有什么问题：

public static boolean isElementinTree(int num, BinaryTreeNode root)
{
    return root != null &&                           //The tree is non-null
           (num == root.getData() ||                 //We have num in this node OR
            isElementInTree(num, root.getLeft()) ||  //We have num in left subtree OR
            isElementInTree(num, root.getRight()) ); //We have num in right subtree
}

score 0 · Accepted Answer

递归解决方案：

boolean isElementinTree (int num, BinaryTreeNode root)
{
  if(root == null)
   return false;

  if(root.value == num)
   return true;

  boolean n1 = isElementinTree(num,root.getLeft());
  boolean n2 = isElementinTree(num,root.getRight());

  return n1 ? n1 : n2;

}

score 0 · Accepted Answer

如果确实在左子树或右子树中找到了要查找的元素，则需要将此事实返回给调用者：

    if (left != null)
    {
        if(isElementinTree(num,left)) return true;
    }
    if (right != null)
    {
        if(isElementinTree(num,right)) return true;
    }

只有当你在左树、右树和当前节点中都没有找到它时，你最终才会落入 final return false。

score 0 · Accepted Answer

您需要检查该值是否在其中一个分支中，并保存该结果。

初始化一个变量boolean found = false;。

当您进行递归调用时，您需要执行以下操作：

found = isElementinTree(num,left)

右侧也一样。

最后，不是返回 false，而是检查是否在分支上找到了该值，只需return found;

另外，首先检查您要查找的号码是否不在节点本身上，而不是先搜索每个分支。只需切换 if 的顺序。

java - 递归搜索二叉树问题

5 回答 5

Related

Reference