如何在Java中查找二叉树中是否存在节点？

Question

我尝试了这个，但是遇到了编译时错误。我错过了什么？如果找不到元素，我还必须返回false。

public boolean search(Node root, Node node){
        if(root==node){
            return true;
        }
        if(root.getLeft()!=null){
            search(root.getLeft(), node);
        }

        if(root.getRight()!=null){
            search(root.getRight(), node);
        }
    }

- testzuser

---

我的回答涵盖了编译错误，但您还有算法错误。我已删除该答案。 - Arnaud Denoyelle

当节点未被找到时会发生什么？ - Vivek Singh

我编辑了答案，以更正算法。 - Arnaud Denoyelle

Answer 1

您遇到了编译错误，因为您没有总是返回某些内容:

    if(root.getLeft()!=null){
        search(root.getLeft(), node);
    }

    if(root.getRight()!=null){
        search(root.getRight(), node);
    }

这将修复编译错误，但不会修正算法:

    if(root.getLeft()!=null){
       return search(root.getLeft(), node);
    }

    if(root.getRight()!=null){
        return search(root.getRight(), node);
    }

这应该可以修复算法：

    if(root.getLeft()!=null && search(root.getLeft(), node)) {
      return true;
    }

    if(root.getRight()!=null && search(root.getRight(), node)){
       return true;
    }
    return false;

- Arnaud Denoyelle

---

如果元素未找到怎么办？我必须返回false。 - testzuser

Answer 2

public boolean search(Node root, Node node){
    if(root == node){
        return true;
    }
    boolean found = false;

    if(root.getLeft() != null ){
        found = search(root.getLeft(), node);
    }

    if(!found && root.getRight() != null )
    {
        found = search(root.getRight(), node);
    }

    return found;
}

- flynn