面试题：给定无父指针的二叉树任意节点，如何找到根节点？

这题我面试时碰到过类似的，核心难点就是没有父指针的情况下，如何从任意子节点回溯到根。下面我给你拆解两种可行的思路，再附上具体代码：

问题先理清楚 #

先再明确下题目：我们手里只有二叉树中某个节点的引用（比如示例里的节点5），Node类没有parent属性，结构如下：

class Node {
    int data;
    Node left;
    Node right;
    Node(int data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

示例的树结构长这样：

1
   / \
  2   3
 / \ / \
4  5 6  7

我们需要实现getParent(Node current)辅助方法，然后通过它找到根节点。

核心思路：利用根节点的唯一性 #

根节点有个独有的特性：没有任何节点的左/右子节点指向它。而其他所有节点，必然是某个节点的左孩子或右孩子。基于这个特性，我们有两种解法：

方法一：哈希集合+BFS遍历（直观好写） #

这种方法思路很直接，适合面试时快速写出来：

1. 先实现getParent：遍历整个树的所有节点，找到哪个节点的左/右子节点等于current，找到就返回这个父节点；如果遍历完都没找到，说明current就是根，返回null。
2. 回溯找根：从给定节点出发，反复调用getParent，直到返回null，最后那个非null的节点就是根。

这里需要注意：遍历整个树的前提是我们能从给定节点出发访问到所有节点（面试题一般默认这个条件成立）。

方法二：快慢指针法（空间优化） #

如果想省掉哈希集合的空间，可以借鉴链表找环的Floyd快慢指针思路（因为从子节点到根的路径是一条单向的“链表”）：

1. 初始化slow和fast两个指针，都指向给定节点。
2. slow每次走一步（调用一次getParent），fast每次走两步（调用两次getParent）。
3. 当fast走到根（getParent(fast)返回null），把slow重置为初始节点，然后两个指针每次都走一步，直到相遇，相遇的节点就是根。

这种方法空间复杂度是O(1)，适合追求最优解的场景。

具体代码实现 #

先写getParent方法（基于BFS遍历） #

这里我们用BFS来遍历整个树，确保不遗漏任何节点：

public Node getParent(Node current, Node startNode) {
    // 先判断当前节点是不是根节点
    if (isRoot(current, startNode)) {
        return null;
    }

    // BFS遍历所有节点找父节点
    Queue<Node> queue = new LinkedList<>();
    Set<Node> visited = new HashSet<>();
    queue.add(startNode);
    visited.add(startNode);

    while (!queue.isEmpty()) {
        Node node = queue.poll();
        // 检查左子节点
        if (node.left != null) {
            if (node.left == current) {
                return node;
            }
            if (!visited.contains(node.left)) {
                visited.add(node.left);
                queue.add(node.left);
            }
        }
        // 检查右子节点
        if (node.right != null) {
            if (node.right == current) {
                return node;
            }
            if (!visited.contains(node.right)) {
                visited.add(node.right);
                queue.add(node.right);
            }
        }
    }
    // 没找到，说明current不在这棵树里
    return null;
}

// 辅助方法：判断当前节点是否是根（没有任何节点的子节点指向它）
private boolean isRoot(Node current, Node startNode) {
    Queue<Node> queue = new LinkedList<>();
    Set<Node> visited = new HashSet<>();
    queue.add(startNode);
    visited.add(startNode);

    while (!queue.isEmpty()) {
        Node node = queue.poll();
        if ((node.left != null && node.left == current) || (node.right != null && node.right == current)) {
            return false;
        }
        // 继续遍历子节点
        if (node.left != null && !visited.contains(node.left)) {
            visited.add(node.left);
            queue.add(node.left);
        }
        if (node.right != null && !visited.contains(node.right)) {
            visited.add(node.right);
            queue.add(node.right);
        }
    }
    return true;
}

再写找根节点的主方法 #

public Node findRoot(Node givenNode) {
    Node current = givenNode;
    Node parent = getParent(current, givenNode);
    // 一直向上找父节点，直到找不到（说明到根了）
    while (parent != null) {
        current = parent;
        parent = getParent(current, givenNode);
    }
    return current;
}

小提示 #

面试时如果时间紧张，优先写第一种方法，直观不容易出错；如果面试官追问空间优化，再拿出快慢指针的思路就行。另外，有些题目可能会简化条件，比如允许你访问整个树的所有节点，那getParent的实现会更简单。

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