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;
}

Answer 1

这就是问题:

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，因为您已经在第一部分中防范了这种情况。