求二叉樹兩節點的最小父節點（有父節點指針）

給定一顆二叉樹，以及其中的兩個node（位址均非空），要求給出這兩個node的一個公共父節點，使得這個父節點與兩個節點的路徑之和最小。描述你程式的最壞時間複雜度，并實作具體函數，函數輸入輸出請參考如下的函數原型：

C++函數原型：

strucy TreeNode{
     TreeNode* left;   //指向左子樹
     TreeNode* right;   //指向右子樹
     TreeNode* father;   //指向父親節點
};
TreeNode* LowestCommonAncestor(TreeNode* first,TreeNode* second){
}
           

思路一：我們首先找到兩個節點的高度差，然後從較靠近根結點的一層開始向上找，若父節點為同一節點則該節點為解。

intgetHeight(TreeNode *node) {
    intheight = 0;
    while(node) {
        height++;
        node = node->parent;
    }
    returnheight;
}
 
TreeNode* LowestCommonAncestor(TreeNode* first,TreeNode* second) {
    intheight1 = getHeight(first), height2 = getHeight(second), diff = height1 - height2;
    if(diff < 0) {
        diff = -diff;
        while(diff--) {
             second = second->parent;
        }
    } else{
        while(diff--) {
            first = first->parent;
        }
    }
    while(first != second) {
        first = first->parent;
        second = second->parent;
    }
    returnfirst;
}
           

思路二：若允許浪費空間，那麼可以用兩個Stack來存儲從first和second到根結點的各個節點，然後出棧時比較位址是否一緻，最後一個位址一緻的節點為解。

兩種方法最壞時間複雜度均為O(n)。