树中两个节点的最低公共祖先

一.树中两个节点的最低公共祖先

题目一：输入两个二叉搜索树的结点，求两个结点的最低公共祖先，所谓的最低公共祖先是指距离两个节点最近的共同祖先。

例如：

解题思路：

1.二叉搜索树具有一个很好的特点。以当前结点为根节点的左边结点的值都是小于根节点的值，右边结点的值都大于根节点的值。
2.根据这个特点，如果给的两个节点的值都小于根节点，那么它们的最低公共祖先就一定在它左子树。
3.如果给的两个节点的值都大于根节点，那么它们的最低公共祖先就一定在它右子树。
4.如果一个结点的值大于根节点的值，一个结点的值小于根节点的值，那么这个根节点就是它的最低公共祖先。
代码实现：

//求两个节点的最低公共祖先(递归解法)
BSTreeNode* GetCommenParent_R(BSTreeNode* root, BSTreeNode* bstn1, BSTreeNode* bstn2)
{
    if (root == NULL || bstn1 == NULL || bstn2 == NULL)
        return NULL;

    if ((bstn1->_data < root->_data) && (bstn2->_data< root->_data))
    {
        GetCommenParent_R(root->_left, bstn1, bstn2);
    }
    else if ((bstn1->_data>root->_data) && (bstn2->_data>root->_data))
    {
        GetCommenParent_R(root->_right, bstn1, bstn2);
    }
    else
        return root;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

题目二：假设在修改一下上述题目的条件，所给的树不是一棵二叉搜索树，甚至不是一棵二叉树，只是一棵简单的树，但是树中的结点存在着指向父节点的指针，那么要怎么求出两个结点的最低公共祖先呢？
这里写图片描述

解决思路：转换题目。

1.假设在上边的树中，题目给出3和78两个结点
2.我们可以发现从树的叶节点到根节点有唯一的一条路径，也就是一条链表
3.3->12->32，78->45->32
4.要求它们的最低公共祖先，就是转换成求上述两条链表的第一个公共结点

求两条链表的第一个公共结点位于我的另一篇博客：

https://weheartit.com/5QkVAOpNOjUHk
https://weheartit.com/UUVryii4I2Q9
https://weheartit.com/uYjLBGRUfWqD

待完成！

转载于:https://my.oschina.net/u/3901811/blog/2051880