java - 递归搜索二叉树

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

您返回从左子树(如果存在)返回的任何内容，而不检查右子树。当 if block 中有 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);
}