4.6 最近公共祖先一题改进方案

[AnnieKim]

我在面试的时候遇到这题两次，也算是高频，所以想在这里提一点可以改进的意见:) 这里假设节点里包含指向父节点的指针parent。 面试的时候，面试官一步步加大难度，最后让我写时间O(n)空间O(1)的方案。我在他的提示下，得到了如下方案，请您过目。 后来面试完我才发现，原来leetcode里已经讲过这个方案了，这是链接。

int getHeight(Node *node) {
    int height = 0;
    while (node) {
        height++;
        node = node->parent;
    }
    return height;
}

Node* first_ancestor(Node* n1, Node* n2){
    int height1 = getHeight(n1), height2 = getHeight(n2);
    if (height1 < height2) {
        swap(height1, height2);
        swap(n1, n2);
    }
    int diff = height1 - height2;
    while (diff--)
        n1 = n1->parent;
    while (n1 != n2) {
        n1 = n1->parent;
        n2 = n2->parent;
    }
    return n1;
}