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

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;   }

以上