找出二叉树祖先节点,二叉树的最近公共父节点
【二叉树】BM38寻找二叉树中两个节点的最近共同祖先——Medium _ 51c to Blog _一棵二叉树有256个节点。
BM38查找二叉树中两个节点的最近共同祖先描述给定一棵二叉树(保证非空)以及此树中两个节点对应的val值o1和o2，请查找o1和o2的最近共同祖先节点。数据范围：树中节点数满足区间[0，n]的要求，节点值val满足区间[0，n]的要求。时间复杂度注意：这个问题保证了二叉树中每个节点的val值是不同的。如果{3，5，1，6，2，0，8，#，#，7，4}，5，1，二叉树{3，5，1，6，2，0，8，#，#，7，4}如下图所示：
因此，节点值为5且节点值为1的节点的最近共同祖先节点的节点值为3，因此对应的输出为3。一个节点本身可以被视为它自己的祖先。
示例1输入：
{3，5，1，6，2，0，8，#，#，7，4}，5，1复制返回值：
3份
2示例输入：
{3，5，1，6，2，0，8，#，#，7，4}，2，7复制返回值：
对于二叉树的任意两个节点，它们到根节点的路径中的第一个相等节点是它们最近的共同祖先节点。我们要做的就是找到从这两个节点到根节点的路径。与BM37中的搜索二叉树不同，我们在普通二叉树中只能通过前序遍历找到到某个节点的路径。因此，这个主题已经成为一种常见的前序遍历类型。实现代码如下：
//https://www . now coder . com/practice/e0cc 33 a 83 AFE 4530 bcec 46 EBA 3325116？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) {}
};
//通过前序遍历保存指定值的搜索路径。
//通过2次搜索，可以比较出它们最近的共同节点。
bool get_path(TreeNode *root，int val，std:vector TreeNode * v)
{
if (root==nullptr)
{
返回false
}
v . push _ back(root)；
if (root- val==val)
{
返回true
}
bool finded=get_path(root- left，val，v)；
如果(找到)
{
返回true
}
finded=get_path(root- right，val，v)；
如果(找到)
{
返回true
}
v . pop _ back()；
返回false
}
int lowestCommonAncestor(TreeNode * root，int o1，int o2)
{
STD:vector TreeNode * path _ 1；
STD:vector TreeNode * path _ 2；
get_path(root，o1，path _ 1)；
get_path(root，o2，path _ 2)；
int I=0；
TreeNode * pre _ node=nullptr
while(I path _ 1 . size()I path _ 2 . size())
{
if (path_1[i]！=path_2[i])
{
返回pre _ node-val；
}
pre _ node=path _ 1[I]；
}
返回pre _ node-val；
}
通过一次递归查找祖先：如果节点o1在根的左/右子树上，或者o1=root，那么根就是o1祖先。
最近共同祖先：如果节点根是o1和o2的共同祖先，而根的左/右子树不是o1和o2的共同祖先，那么根就是o1和o2最近公布的祖先。
想法：
1.通过后续遍历确定一个节点包含o1还是o22。在后续的遍历过程中，先确定左子树，再确定右子树，最后确定根节点。3.如果左子树不包含o1和o2，那么o1和o2都在右子树中，或者当前节点是o1和o2的共同节点。a .如果当前节点不等于o1和o2，那么右边的子树就是o1和o2的共同节点。但它可能不是最近的共同祖先节点，所以我们需要递归查找右边的子树b，如果当前节点等于o1或o2，那么当前节点就是最近的共同子节点。
TreeNode *find(TreeNode *root，int o1，int o2)
{
if (root==nullptr)
{
返回nullptr
}
if(根值==o1 根值==o2)
{
返回根目录；//当前节可能是最近的共同祖先节点，或者当前节点是o1，o2
}
auto left=find(root- left，o1，O2)；//找到左边的子树
auto right=find(root- right，o1，O2)；//找到正确的子树
If (left==nullptr)//如果在左子树中没有找到o1和o2，那么右子树一定是它们的共同祖先。
{
向右返回；
}
if (right==nullptr)
{
向左返回；
}
返回根目录；//如果左子树和右子树都找到o1或o2，则根节点是它们的共同祖先节点。
}
int lowestCommonAncestor _ 1(TreeNode * root，int o1，int o2)
{
返回find(root，o1，O2)-val；
}
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。