hawstein/cracking-the-coding-interview

Solutions for the book: Cracking the coding interview V4. Written in C++.

Solutions for the book: Cracking the coding interview V4. Written in C++.

See the detailed solutions:

http://hawstein.com/2013/03/14/ctci-solutions-contents/

cracking-the-coding-interview's Issues

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

我在面试的时候遇到这题两次，也算是高频，所以想在这里提一点可以改进的意见:)
这里假设节点里包含指向父节点的指针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;
}

Program 3.2

In stack operations don't we have to include header file for program to recognize push(), pop() operations? Also my program was complaining when I delcared s1, s2 in private. I did stack s1; stack s2 for proper execution. Please advise