在一棵二叉搜索树上查找63,二叉排序树公共祖先
BM37二叉查找树最近的共同祖先
知识点树递归
给定一个二叉查找树，查找树中两个指定节点的最近的共同祖先。1.这个问题的最近共同祖先的定义：对于有根树T的两个节点p和q，最近共同祖先LCA(T，p，q)表示一个节点x，满足x是p和q的祖先且x的深度尽可能大。在这里，一个节点也可以是它自己的祖先。2.二叉查找树意味着如果它的左子树不为空，那么左子树中所有节点的值都小于它的根节点的值；如果其右子树不为空，则右子树中所有节点的值都大于其根节点的值。3.所有节点的值都是唯一的。4.p和Q是不同的节点，并且都存在于给定的二叉查找树中。数据范围：3=节点总数=100000=节点值=10000如果给定以下搜索二叉树：{7，1，12，0，4，11，14，#，#，3，5}，如下图：
示例1输入：
{7,1,12,0,4,11,14,#,#,3,5},1,12
复制返回值：
七
复制描述：
节点1和节点12最近的共同祖先是7。
2示例输入：
{7,1,12,0,4,11,14,#,#,3,5},12,11
复制返回值：
12
复制描述：
因为节点也可以是它自己的祖先，所以输出12
通过获取路径进行比较来解决问题：
1.获取指定节点的路径。2.比较路径上的节点。第一个不同的先前节点是它们最近的共同祖先，或反向比较。第一个相同的是他们最近的共同祖先。这里使用反向比较，而不是保存前一个节点。
//https://www . now coder . com/practice/d 9820119321945 f 588 ed6 a 26 f 0 a 6991 f？tpId=295 tags=title=难度=0判断状态=0 rp=0来源URL=/考试/oj
#包含位/标准数据。h
定义树结构
{
int val
struct TreeNode * left
struct TreeNode * right
TreeNode(int x) : val(x)，left(nullptr)，right(nullptr) {}
};
STD:vector TreeNode * find(TreeNode * root，int val)
{
STD:vector TreeNode * v；
auto node=root
while (node- val！=val)
{
v.push_back(节点)；
if(节点值值)
{
node=节点右；
}
其他
{
node=节点-左侧；
}
}
v.push_back(节点)；
回归v；
}
int lowestCommonAncestor(TreeNode * root，int p，int q)
{
auto a=find(root，p)；
auto b=find(root，q)；
if (a.size() b.size())
{
a .互换(b)；
}
for(int I=a . size()-1；I=0；-我)
{
for(int k=b . size()-1；k=0；k -)
{
if (a[i]==b[k])
{
返回一个[I]-val；
}
}
}
返回p；
}
通过一次遍历获得最近的共同祖先。对于一棵搜索二叉树，给定两个值A和B，在遍历该树的过程中，我们假设当前节点的值为X，我们有如下结论：
1.a等于x或者b等于x:那么当前节点一定是a和b 2最近的共同祖先。a x和b x或者a x和b x:表示当前节点在搜索的过程中刚好在当前节点分叉，所以当前节点是他们最近的共同祖先。3.a和b都小于x:这意味着它们最近的共同祖先在x ^ 4的左节点大于x。a和b:它们在x右节点最近的共同祖先的代码实现如下：
int lowestCommonAncestor _ r(TreeNode * root，int p，int q)
{
if(根值==p 根值==q)
{
返回根值；
}
if(根值p根值q)
{
返回lowestCommonAncestor_r(根左，p，q)；
}
if(根值p根值q)
{
返回lowestCommonAncestor _ r(root-right，p，q)；
}
返回根值；
}
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。