树：二叉树的公共祖父节点

1.如果这棵二叉树是二叉查找树，那么记录根节点到x和y节点的路径问题变得很简单，借助于二叉查找树的性质，借助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.若一棵树是普通的二叉树，则二叉排序树在查找方面的特性不能应用。在普通二叉树中，寻找从根节点到任意节点的路径不像是在BST中那么简单，我们先要解决这个问题。

用vector存储路径，然后确定当前节点相同，下一个节点不相同的节点。

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();//在该子树上查找失败，则删除这个根节点  
     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];  
}

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

假如有父亲指针：这种情况比较简单，计算两个结点的深度，再把深度大的向上移，移到同一深度。在同时向上移动，直到两个结点相同，这样便找到了父节点。这个算法时间复杂度为O(N)。

struct Node  
{  
    int data;  
    Node* left;  
    Node* right;  
    Node* parent;  
    Node() :left(NULL), right(NULL), parent(NULL)  
    {}  
};  
int getDpeth(Node *n)//结点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、没有父指针

首先从根节点开始向下找，如果根节点等于其中一个子节点，那么根节点便是最近公共父结点。否则计算左子树和右子树中包含n1或n2的个数。如果左子树包含n1、n2那么最近公共父结点在左子树，如果右子树包含n1和n2，那么在右子树。如果左右子树各包含一个，那么最近公共父结点就是当前结点。如果二叉树是平衡的，那么算法复杂度为O(logN)。最坏情况就是树成了链表，算法时间负责度为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的个数  
    if (count == 1)  
        return root;//左子树一个，右子树肯定也有一个  
    else if (count == 2)//都在左子树  
        return findLCA(root->left, n1, n2);  
    else//都在右子树  
        return findLCA(root->right, n1, n2);  
}

优化解法：还有一种方法，从下向上找。如果找到n1或n2，就把它传给它的父结点，如果向下到头都没有找到，那么返回NULL。如果当前结点左右子树都返回非NULL，那么当前结点就是最近公共父结点。这样只需要遍历一遍，算法时间复杂度为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);//右子树  
    //当前结点左右子树都找到了n1和n2，那么这个结点就是LCA结点  
    if (L != NULL&R != NULL)  
        return root;  
    //否则是不为NULL的结点，或者两个都为NULL  
    else  
        return L !=NULL ? L : R;  
}

以上