递归搜索二叉树

Question

您好，我无法使这段代码正常工作。当它一直递归到树的最左边缘时，它似乎要跳出堆栈。我就是想不通这个。

public static Node lookup(Node node, int lookupValue) {

        if (node == null)  {
            return null;
        } else {
            if (node.value == lookupValue) {
                System.out.println("Found");
                return node;
            } else if(node.left != null) {
                return lookup(node.left, lookupValue);

            } else if(node.right != null) {
                return lookup(node.right, lookupValue);
            } else {
                return null;
            }
        }
}

Answer 1

你 return 从左子树（如果存在）中 return 编辑的任何东西，而不检查右子树。当 if 块中有 return 语句时，不需要很多 else 分支。变化如下：

public static Node lookup(Node node, int lookupValue) {
    if (node == null)
        return null;
    if (node.value == lookupValue)
        // System.out.println("Found");
        return node;
    Node rval = lookup(node.left, lookupValue);
    // only return if found in left sub-tree
    return (rval != null) ? rval : lookup(node.right, lookupValue);
}

Answer 2

你的else if不正确你应该每次检查左右：

if (node == null) return null;
if (node.value == lookupValue) {
    System.out.println("Found");
    return node;
}
Node found = lookup(node.left, lookupValue);
if(found != null) {
    return found;
}
return lookup(node.right, lookupValue);

递归搜索二叉树

Searching binary tree recursively

java

lookup

tree

recursion