[LeetCode]Lowest Common Ancestor of a Binary Search Tree-白红宇的个人博客

[LeetCode]Lowest Common Ancestor of a Binary Search Tree

发布日期：2021-11-22 02:48:44 浏览次数：2 分类：技术文章

本文共 1613 字，大约阅读时间需要 5 分钟。

问题：

给定一个二叉树，找到两个节点NA， NB的最近公共祖先(LCA)。

比如对于下图，4 和 7 的 LCA 是6， 1和13的LCA 是 8。

分析：

我们这里先考虑一般的二叉树(BT)，然后再考虑这个二叉树是二叉搜索树(BST)的情况。

查找两个node的最早的公共祖先，分三种情况：

1. 如果两个node在root的两边，那么最早的公共祖先就是root。

2. 如果两个node在root的左边，那么把root.leftChild作为root，再递归。

3. 如果两个node在root的右边，那么把root.rightChild作为root，再递归。

那么我们如何知道能否通过原始节点到达某一个节点呢？这里我们需要定义一个递归函数covers (Node root, Node node)，让root的左右子节点不断的调用这个函数，如果某一个子节点就是要找到的节点，那么返回true，否则返回false. 具体代码如下：

[java]
 /* 
      * check whether the node n is in the tree 
      */  
     private static boolean covers(Node rootNode, Node n) {  
         if(rootNode == null) return false;  
         if(rootNode == n) return true;  
         return covers(rootNode.leftChild, n) || covers(rootNode.rightChild, n);  
     }  

有个covers这个函数，我们要实现前面三种不同的情况，那就简单了。代码如下：

[java]
 /* 
      * get the first common ancestor of node p and node q 
      */  
     public static Node commonAncestor(Node rootNode, Node p, Node q) {  
         // case 2  
         if (covers(rootNode.leftChild, p) && covers(rootNode.leftChild, q))  
             return commonAncestor(rootNode.leftChild, p, q);  
         //case 3  
         if (covers(rootNode.rightChild, p) && covers(rootNode.rightChild, q))  
             return commonAncestor(rootNode.rightChild, p, q);  
         //case 1  
         return rootNode;  
     }  

如果这个二叉树是BST，那么我们可以利用BST的特点，把根节点的值与两个节点的值进行比较，如果两个节点的值都比根节点的值小，那么一定在根节点的左边，所以我们把根节点的左子节点作为起始点，然后递归。如果两个节点的值都比祖先节点的值大，那么一定在根节点的右边，所以我们把根节点的右子节点作为起始点，然后递归，如果上面两张情况都不是，那么很明显，这个根节点就是LCA. 代码如下：

[java]
 public Node LCA(Node root, Node p, Node q) {  
   if (root == null || p == null || q == null ) return NULL;   
   if (max(p.data, q.data) < root.data)  
     return LCA(root.left, p, q);  
   else if (min(p.data, q.data) > root.data)  
     return LCA(root.right, p, q);  
   else  
     return root;  
 }  

备注：这里并没有考虑 p 和 q 不在 BST里的情况。

参考：

转载地址：https://blog.csdn.net/zxdfc/article/details/48030265 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：[LeetCode94]Binary Tree Inorder Traversal

下一篇：异常图结构

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章