java - 在二叉树中查找给定键的父级

Question

我试图在二叉树(不是 BST)中找到给定键的父键。这段代码总是返回null，有人能告诉我问题出在哪里吗？我认为问题是即使我返回parent，它仍然会返回null。谢谢:)

public Node getParent(int key,Node parent, Node r){
    if(r!=null){
        if(r.iData==key)
            return parent;
        getParent(key, r, r.leftChild);
        getParent(key, r, r.rightChild);
    }
        return null;
}

Answer 1

您正在递归到左子树和右子树，但是当这些调用找到匹配项时，您只需忽略它。相反，做类似的事情

public Node getParent(int key, Node parent, Node r) {
    if (r!=null) {
        if (r.iData == key)
            return parent;
        Node p;
        p = getParent(key, r, r.leftChild);
        if (p != null)
            return p;
        p = getParent(key, r, r.rightChild);
        if (p != null)
            return p;
    }
    return null;
}