设计一个算法,找出二叉树中某两个结点的第一个公共祖先.。不得将额外的结点存储在另外的数据结构中。注意:这不一定是二叉查找树。
设计一个算法,找出二叉树中某两个结点的第一个公共祖先.。不得将额外的结点存储在另外的数据结构中。注意:这不一定是二叉查找树。
一贱书生 发表于1年前
设计一个算法,找出二叉树中某两个结点的第一个公共祖先.。不得将额外的结点存储在另外的数据结构中。注意:这不一定是二叉查找树。
  • 发表于 1年前
  • 阅读 1034
  • 收藏 0
  • 点赞 0
  • 评论 0

新睿云服务器60天免费使用,快来体验!>>>   

题目分析:

假设1:这个二叉树是二叉排序树(O(N))

      如果题目中的二叉树是二叉排序树,那么这道题目变的相对简单很多,我们只需要从根节点开始遍历,有以下三种情况发生:

      (1)如果题目给的两个节点的值都大于当前节点,那么继续遍历当前节点的右子树

      (2)如果题目给的两个节点的值都小于当前节点,那么继续遍历当前节点的左子树

      (3)如果当前节点大于其中一个节点而小于其中另外一个节点,那么则返回该节点,该节点便是两个节点的公共                  祖先节点。

假设2:这个二叉树是普通的二叉树,但是存在指向父节点的指针

       由于每个节点存在指向父节点的指针,所以如果给定任意一个节点,便可以找到从该节点到根节点的路径,因此我们可以找到题目中给予的两个节点分别到根节点的路径,因此该题目便变成了求两个单向链表的第一个公共节点。

假设2延伸:求两个单向链表第一个公共节点有两种方法:

      (1)第一种方法是:两个链表如果有 公共节点,那么从第一个公共节点开始往后的所有节点都相同,我们首先遍历两个链表,求出两个链表的长度。然后设定两个指针分别指向这两个单向链表的头结 点,首先让链表较长的指针先移动,直至移动的剩余长度与链表较短的那个链表长度相同为止,这个时候两个指针开始同时移动,直到两个指针指向的节点相同,这 个节点便是这两个单向链表的第一个公共节点。

      (2)第二种方法是:可以设置两个栈,首先分别把两个链表中的节点依次入栈,接下来从两个栈中同时一个一个的将节点弹出,遇到第一对弹出的节点不同时,那么前一次弹出相同的节点便是这两个链表的第一个公共节点。

 

假设3:这个二叉树是普通的二叉树,并且不存在指向父节点的指针

<方法1>:判断子树中是否存在某节点(时间复杂度O(N^2))

          首先建立一个方法判断一棵树中是否存在某个节点,这个比较简单,只需要遍历整棵树,如果存在返回true,如果不存在则返回false。

      接下来的判断过程就相当于二叉排序数的判断过程了,只不过二叉排序树判断一个节点是否在左子树或者右子树中只需要和父节点比较,而普通的树需要遍历整个左子树或者右子树才能实现, 

 

      (1)如果题目给的两个节点都在右子树,那么继续遍历当前节点的右子树

      (2)如果题目给的两个节点都在左子树,那么继续遍历当前节点的左子树

      (3)如果给定的两个节点一个在左子树,一个在右子树,则返回当前节点。

<方法2>:寻找从根节点到子节点的路径

        如果找到从根节点到两个子节点的路径,那么题目就迎刃而解了,可以用栈遍历二叉树,最后找到从根节点到相应节点的路径,类似二叉树的先序非递归遍历一样,先遍历根节点,接着遍历左子树,接着遍历右子树,直到遍历到相应节点为止,这时栈中的元素便是路径元素。

<方法3>:递归遍历

      设根节点为root,两个节点分别为p,q,用前序遍历方法递归遍历整个二叉树,如果只找到p则返回p,如果只找到q则返回q,如果一个节点的左右子树分别找到p,q,则返回该节点,其他情况返回NULL。

 

 

 

 

 

 

/*
*若p为root的子孙,则返回true
*/
boolean covers(TreeNode root,TreeNode p)
{
if(root==null) return false;
if(root== p) return true;
return covers(root.left,p)||covers(root.right,p);
}
    TreeNode commonAncestorHelper(TreeNode root,TreeNode p,TreeNode q)
    {
    if(root==null) return null;
    if(root == p || root == q) return root;
    boolean is_p_on_left=covers(root.left,p);
    boolean is_q_on_left=covers(root.left,q);
    /*
    * 若p和q不在同一边,则返回root
    */
    if(is_p_on_left!=is_q_on_left) return root;
    /*
    * 否则就在同一边,遍访那一边
    */
    TreeNode child_side=is_p_on_left?root.left:root.right;
    return commonAncestorHelper(child_side,p,q);
    }
TreeNode commonAncestor(TreeNode root,TreeNode p,TreeNode q)
{
if(!covers(root,p)||!covers(root,q))//错误检查
{
return false;
}
return commonAncestorHelper(root,p,q);
}

  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 17
博文 722
码字总数 600072
×
一贱书生
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: