0

这是我的 find() 方法：

public boolean find(int key) {

    BinTreeNode node = findHelper(key, root);
    if (node == null) {
        return false;
    } else {
        return true;
    }
}    


private BinTreeNode findHelper(int key, BinTreeNode node) {
    if (node == null) {
        return null;
    }    
    if(key == node.item) {
        return node;
    }
    else if(key < node.item) {
        return findHelper(key,node.leftChild);
    }
    else {
        return findHelper(key,node.rightChild);
    }
}

这是我修改后的代码。它仍然不起作用:(

public boolean searchNum(BinTreeNode node, int num) {
    if(node == null) {
        return false;
    }
    else {

        int result = num - node.item;
        if(find(result)) {
            return true; 
        }

        if(node.leftChild != null) {
            searchNum(node.leftChild, num);
        }

       if(node.rightChild != null) {
            searchNum(node.rightChild, num);
        } 

       return false;
    }
}

我正在尝试查找给定数字是否等于二叉搜索树中任意 2 个数字的总和。我知道错误在哪里，但我不知道如何纠正它。

以下几行

if(find(result)) {

return true; 

}

应该终止该方法，因为一旦我得到一个真实的，这就是我所需要的，我应该将值返回给调用函数。但是，递归继续执行，最终返回最后一次递归调用的值。请帮忙。

public boolean searchNum(BinTreeNode node, int num) {
    if(node == null) {
        return false;
    }
    else {
        if(node.leftChild != null) {
            searchNum(node.leftChild, num);
        }
        int result = num - node.item;
        System.out.println(node.item);
        //I have a separate find() which finds if the key is in the tree
        if(find(result)) {
            return true; 
        }

       if(node.rightChild != null) {
            searchNum(node.rightChild, num);
        } 

       return false;
    }
}
}
4

2 回答 2

1

find在递归检查树的左侧之前尝试移动检查。否则，您甚至会在检查节点本身之前从每个节点的左侧向下走。

else {
    // Moved to the top of the else
    int result = num - node.item;
    System.out.println(node.item);
    if(find(result)) {
        return true; 
    }
    // Then check recursively
    if(node.leftChild != null) {
        searchNum(node.leftChild, num);
    }
    if(node.rightChild != null) {
        searchNum(node.rightChild, num);
    } 

   return false;
}
于 2013-09-19T16:06:45.950 回答
1

最一般的递归公式如下：

function sampleRecursion(a){
    if(isTerminalCase) {
        return true;
    }
    else {
       a = modify(a);
       return sampleRecursion(a);
    }
}

使用它作为你的代码模板，你应该有这样的东西：

public boolean searchNum(BinTreeNode node, int num) {
    //validate the input
    if(node == null) {
        return false;
    }
    //this is your terminal case
    int result = num - node.item;
    //I have a separate find() which finds if the key is in the tree
    if(find(result)) {
        return true; 
    }
    //this if doesn't make any sense as you validate this input already
    //if(node.leftChild != null) {
    //    searchNum(node.leftChild, num);
    //}
    //here is where we are returning the value we get back from searchNum
    return seachNum(node.leftChild, num) || searchNum(node.rightChilde, num);
    //System.out.println(node.item);
    //I moved this up into the single return case, so everything after this is unnecessary
    //if(node.rightChild != null) {
    //    searchNum(node.rightChild, num);
    //} 
    //return false;
}

所以，清理干净，应该是这样的：

public boolean searchNum(BinTreeNode node, int num) {
    //validate the input
    if(node == null) {
        return false;
    }
    //this is your terminal case
    int result = num - node.item;
    //I have a separate find() which finds if the key is in the tree
    if(find(result)) {
        return true; 
    }
    //here is where we are returning the value we get back from searchNum
    return seachNum(node.leftChild, num) || searchNum(node.rightChilde, num);
}

这是您的递归函数应该是什么样子的近似值。我不知道 find 功能是做什么的，所以我不知道它是否符合您的要求。

此外，根据您的描述，您试图在搜索树中使用两个数字，而不是一个。在您现在拥有的代码中，您只使用了一个。所以如果你传入，比如说，({a node}, 15)，你会得到……一些东西。如果你的 find 函数调用 searchNum({top node}, result)，我想你会没事的。但我不知道 find 是做什么的，所以我不能肯定地说。

编辑：合并find和findHelper.

private boolean find(int key, BinTreeNode node) {
    if (node == null) {
        return false;
    }    
    if(key == node.item) {
        return true;
    }
    else if(key < node.item) {
        return findHelper(key,node.leftChild);
    }
    else {
        return findHelper(key,node.rightChild);
    }
}

searchNum然后只需调用它find(result, root)。也就是说，如果您有权访问 root in searchNum。

于 2013-09-19T16:26:52.683 回答