在二叉树中查找节点

Question

我有一个问题,一个方法应该在二叉树中找到一个包含给定的节点value.下面提供的方法不起作用,问题是为什么.

public Node search(Node node, int value) {
    if(node.value == value) return node;
    if(node.left != null) search(node.left, value);
    if(node.right != null) search(node.right, value);
    return null;
}

问题是,null当value树中实际存在给定节点时,此方法有时会返回.这是为什么？

Answer 1

你不应该忽略递归调用返回的值,并且你的方法不应该使用root,但传递的是node:

public Node search(Node node, int value) {
    if(node.value == value) return node;
    Node found = null;
    if(node.left != null)
        found = search(node.left, value);
    if(found == null && node.right != null)
        found = search(node.right, value);
    return found;
}