如何实现二叉树中查找指定子节点父节点的函数？

嗨，看你正在写这个二叉树的父节点查找函数，我来帮你补全并理清楚实现逻辑~

首先咱先明确需求：给定二叉树根节点和一个目标子节点，返回它的父节点；如果目标就是根节点，直接返回null。

核心思路 #

不管用递归还是迭代，核心逻辑都是一样的：

• 先处理特殊情况：如果树为空，或者目标节点就是根节点，直接返回null
• 遍历二叉树的每个节点，检查当前节点的左、右子节点是否是目标节点，如果是，当前节点就是咱要找的父节点
• 如果当前节点不是，就继续遍历它的子树

递归实现版本（简洁直观） #

先假设你的BinTreeNode结构大概是这样（如果和你的实际结构有出入，调整字段名即可）：

class BinTreeNode<T> {
    T data;
    BinTreeNode<T> left;
    BinTreeNode<T> right;

    public BinTreeNode(T data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

然后补全你的Parent函数：

public static BinTreeNode<Character> Parent(BinTreeNode<Character> bt, BinTreeNode<Character> target) {
    // 特殊情况：树为空，或者目标就是根节点，直接返回null
    if (bt == null || bt == target) {
        return null;
    }

    // 检查当前节点的直接子节点是不是目标
    if (bt.left == target || bt.right == target) {
        return bt;
    }

    // 递归遍历左子树找父节点，找到就返回
    BinTreeNode<Character> leftParent = Parent(bt.left, target);
    if (leftParent != null) {
        return leftParent;
    }

    // 左子树没找到，递归遍历右子树
    return Parent(bt.right, target);
}

迭代实现版本（适合深度很大的树，避免递归栈溢出） #

如果你的二叉树深度特别大，递归可能会触发栈溢出，这时候可以用层序遍历（队列实现）的迭代方式：

import java.util.LinkedList;
import java.util.Queue;

public static BinTreeNode<Character> ParentIterative(BinTreeNode<Character> bt, BinTreeNode<Character> target) {
    if (bt == null || bt == target) {
        return null;
    }

    // 用队列存储待遍历的节点
    Queue<BinTreeNode<Character>> queue = new LinkedList<>();
    queue.offer(bt);

    while (!queue.isEmpty()) {
        BinTreeNode<Character> current = queue.poll();

        // 检查左子节点
        if (current.left != null) {
            if (current.left == target) {
                return current;
            }
            queue.offer(current.left);
        }

        // 检查右子节点
        if (current.right != null) {
            if (current.right == target) {
                return current;
            }
            queue.offer(current.right);
        }
    }

    // 如果目标节点不在树中，返回null（也可以根据需求抛出异常）
    return null;
}

几个关键点要注意 #

• 节点判断方式：上面的代码是通过对象引用（==）判断是否是目标节点，如果你的需求是根据节点的值来判断，要把==改成值比较，比如bt.left.data.equals(target.data)，但要注意先判断子节点不为null，避免空指针异常
• 异常情况：如果目标节点不在二叉树中，两个版本都会返回null，你可以根据实际需求改成抛出异常或者返回特定标识
• 空树处理：开头的bt == null判断能避免传入空树时出现空指针问题

内容的提问来源于stack exchange，提问作者Karoline