剑指Offer Java版 面试题68：树中两个节点的最低公共祖

题目：输入两个树节点，求它们的最低公共祖先。

参考答案

class TreeNode<T> {
    T value;
    List<TreeNode<T>> children;
    
    public TreeNode(T value) {
        this.value = value;
        children = new ArrayList<>();
    }
}

public <T> TreeNode<T> getLastCommonParent(TreeNode<T> root, TreeNode<T> node1, TreeNode<T> node2) {
    if (root == null || node1 == null || node2 == null) {
        return null;
    }
    LinkedList<TreeNode<T>> path1 = new LinkedList<>();
    getNodePath(root, node1, path1);
    LinkedList<TreeNode<T>> path2 = new LinkedList<>();
    getNodePath(root, node2, path2);
    return getLastCommonNode(path1, path2);
}

private <T> boolean getNodePath(TreeNode<T> root, TreeNode<T> node, LinkedList<TreeNode<T>> path) {
    if (root == node) {
        return true;
    }
    path.add(root);
    boolean found = false;
    for (int i = 0; !found && i < root.children.size(); i++) {
        found = getNodePath(root.children.get(i), node, path);
    }
    if (!found) {
        path.removeLast();
    }
    return found;
}

private <T> TreeNode<T> getLastCommonNode(LinkedList<TreeNode<T>> path1, LinkedList<TreeNode<T>> path2) {
    Iterator<TreeNode<T>> iterator1 = path1.iterator();
    Iterator<TreeNode<T>> iterator2 = path2.iterator();
    TreeNode<T> last = null;
    while (iterator1.hasNext() && iterator2.hasNext()) {
        TreeNode<T> node = iterator1.next();
        if (node == iterator2.next()) {
            last = node;
        } else {
            break;
        }
    }
    return last;
}

复杂度分析

• 时间复杂度：O(n)。
• 空间复杂度：O(logn)。

👉剑指Offer Java版目录
👉剑指Offer Java版专题