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;
}首先从根节点开始向下找，如果根节点等于其中一个子节点，那么根节点便是最近公共父结点。否则计算左子树和右子树中包含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;
}以上
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
