樹：二叉樹的公共祖父節(jié)點(diǎn)

1.如果這棵二叉樹是二叉查找樹，那么記錄根節(jié)點(diǎn)到x和y節(jié)點(diǎn)的路徑問題變得很簡單，借助于二叉查找樹的性質(zhì)，借助BST的查找過程，很簡單便可以做到。

void find1(TreeNode* root,TreeNode* p,vector<TreeNode*> &v)  
{  
     if(root == p)  
     {  
         v.push_back(root);   
         return ;  
     }  
     if(p->val > root->val)  
     {  
         v.push_back(root);  
         find1(root->right,p,v);   
     }   
     else  
     {  
         v.push_back(root);  
         find1(root->left,p,v);   
     }  
}

-------------------------------------------------------------------------------------------

2.若一棵樹是普通的二叉樹，則二叉排序樹在查找方面的特性不能應(yīng)用。在普通二叉樹中，尋找從根節(jié)點(diǎn)到任意節(jié)點(diǎn)的路徑不像是在BST中那么簡單，我們先要解決這個問題。

用vector存儲路徑，然后確定當(dāng)前節(jié)點(diǎn)相同，下一個節(jié)點(diǎn)不相同的節(jié)點(diǎn)。

bool findP(TreeNode *root,TreeNode *p,vector<TreeNode*> &v)//遞歸查找，路徑記錄在v中  
{  
     if(p==NULL || root == NULL)  
     return false;  
     v.push_back(root);  
     if(root == p)  
     return true;  
     if(root->left != NULL && findP(root->left,p,v) == true )  
     {  
         return true;  
     }  
     if(root->right != NULL && findP(root->right,p,v) == true)  
     {  
        return true;  
     }  
     v.pop_back();//在該子樹上查找失敗，則刪除這個根節(jié)點(diǎn)  
     return false;  
}

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)   
{  
      if(root == NULL || p == NULL || q == NULL)  
      {  
              return NULL;  
      }  
      vector<TreeNode *> v1;  
      findP(root,p,v1);  
      vector<TreeNode*> v2;  
      findP(root,q,v2);  
      int len = v1.size()<v2.size()?v1.size():v2.size();  
      int i = 0;  
      for(i = 0;i<len-1;i++)  
      {  
          if(v1[i] == v2[i] && v1[i+1]!=v2[i+1])  
          break;  
      }  
      return v1[i];  
}

-------------------------------------------------------------------------------------------

假如有父親指針：這種情況比較簡單，計算兩個結(jié)點(diǎn)的深度，再把深度大的向上移，移到同一深度。在同時向上移動，直到兩個結(jié)點(diǎn)相同，這樣便找到了父節(jié)點(diǎn)。這個算法時間復(fù)雜度為O(N)。

struct Node  
{  
    int data;  
    Node* left;  
    Node* right;  
    Node* parent;  
    Node() :left(NULL), right(NULL), parent(NULL)  
    {}  
};  
int getDpeth(Node *n)//結(jié)點(diǎn)n到根節(jié)點(diǎn)深度  
{  
    int count = 0;  
    while (n)  
    {  
        ++count;  
        n = n->parent;  
    }  
    return count;  
}  
Node* findNearestCommonAncestor(Node* n1, Node* n2)  
{  
    int depth2 = getDpeth(n1);  
    int depth3 = getDpeth(n2);  
  
    //移動同一深度  
    while (depth2 > depth3)  
    {  
        n1 = n1->parent;  
        --depth2;  
    }  
    while (depth2 < depth3)  
    {  
        n2 = n2->parent;  
        --depth3;  
    }  
    //向上找  
    while (n1 != n2)  
    {  
        n1 = n1->parent;  
        n2 = n2->parent;  
    }  
    return n1;  
}

2、沒有父指針

首先從根節(jié)點(diǎn)開始向下找，如果根節(jié)點(diǎn)等于其中一個子節(jié)點(diǎn)，那么根節(jié)點(diǎn)便是最近公共父結(jié)點(diǎn)。否則計算左子樹和右子樹中包含n1或n2的個數(shù)。如果左子樹包含n1、n2那么最近公共父結(jié)點(diǎn)在左子樹，如果右子樹包含n1和n2，那么在右子樹。如果左右子樹各包含一個，那么最近公共父結(jié)點(diǎn)就是當(dāng)前結(jié)點(diǎn)。如果二叉樹是平衡的，那么算法復(fù)雜度為O(logN)。最壞情況就是樹成了鏈表，算法時間負(fù)責(zé)度為O(N^2)。

int countMatch(Node *current, Node* n1, Node* n2)  
{  
    if (current == NULL)  
        return 0;  
    int count = countMatch(current->left, n1, n2) + countMatch(current->right, n1, n2);  
    if (current == n1 || current == n2)  
        return 1 + count;  
    return count;     
}  
Node* findLCA(Node* root, Node* n1, Node* n2)  
{  
    if (root == NULL)  
        return NULL;  
    if (root == n1 || root == n2)  
        return root;  
    int count = countMatch(root->left, n1, n2);//左子樹包含n1和n2的個數(shù)  
    if (count == 1)  
        return root;//左子樹一個，右子樹肯定也有一個  
    else if (count == 2)//都在左子樹  
        return findLCA(root->left, n1, n2);  
    else//都在右子樹  
        return findLCA(root->right, n1, n2);  
}

優(yōu)化解法：還有一種方法，從下向上找。如果找到n1或n2，就把它傳給它的父結(jié)點(diǎn)，如果向下到頭都沒有找到，那么返回NULL。如果當(dāng)前結(jié)點(diǎn)左右子樹都返回非NULL，那么當(dāng)前結(jié)點(diǎn)就是最近公共父結(jié)點(diǎn)。這樣只需要遍歷一遍，算法時間復(fù)雜度為O(N)。

Node* findLCA(Node *root, Node* n1, Node* n2)  
{  
    if (root == NULL)//沒找到  
        return NULL;  
    if (root == n1 || root == n2)//找到  
        return root;  
    Node* L = findLCA(root->left, n1, n2);//左子樹  
    Node* R = findLCA(root->right, n1, n2);//右子樹  
    //當(dāng)前結(jié)點(diǎn)左右子樹都找到了n1和n2，那么這個結(jié)點(diǎn)就是LCA結(jié)點(diǎn)  
    if (L != NULL&R != NULL)  
        return root;  
    //否則是不為NULL的結(jié)點(diǎn)，或者兩個都為NULL  
    else  
        return L !=NULL ? L : R;  
}

以上