二叉树的最低公共祖先

17 Mar 2025 | 4 分钟阅读

二叉树的最低公共祖先代表什么？

树中包含 n1 和 n2 均为其后代的最低节点是最低公共祖先（LCA），而 n1 和 n2 是我们正在寻找 LCA 的节点。因此，位于离根节点最远的 n1 和 n2 节点的公共祖先是包含 n1 和 n2 的二叉树的 LCA。

LCA（最低公共祖先）的应用

树中节点对之间的距离可以计算为根到 n1 的距离加上根到 n2 的距离减去根到其最低公共祖先距离的两倍。

示例

方法 -

我们知道，因为这是一个二叉搜索树，左子节点将小于或等于根节点，而右子节点将大于根节点。本质上，这涉及到检查以下边缘情况
如果根为空，则返回 null。
如果其中一个节点是根节点（最低公共祖先），则 LCA 是根节点。
如果一个节点大于根节点而另一个节点小于根节点，则根节点是 LCA。
如果提供的两个节点相同，则不存在 LCA。返回 null。
如果两个节点都小于根节点，则迭代调用 LCA 函数以在根节点的左子节点上计算步骤 1 到 4。
如果两个节点都大于根节点，则迭代调用 LCA 函数以在根节点的右子节点上计算步骤 1 到 4。

C++ 程序

使用单次遍历的递归方法

时间复杂度

O(n)

空间复杂度

O(n)

打印 LCA 的函数

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==NULL) return NULL ; 
        //if i get p i will return it 
        if(root==p) return p ;
        //if i get q i will return it 
        if(root==q) return q ;
 
      //make left call 
      TreeNode*leftcall = lowestCommonAncestor(root->left,p,q) ; 
      //make right call 
     TreeNode*rightcall = lowestCommonAncestor(root->right,p,q) ;

         //if at a node both leftcall and rightcall returned NULL--> return NULL
         if(leftcall==NULL and rightcall==NULL)  return NULL ; 


         //if at a node leftcall returns found node and rightcall returned NULL--> return leftcall
         if(leftcall!=NULL and rightcall==NULL)  return leftcall ; 

      //if at a node leftcall returned NULL and rightcall returned found node--> return rightcall
         if(leftcall==NULL and rightcall!=NULL)  return rightcall ; 

      //if at a node both leftcall and rightcall returned found node--> return current node
         if(leftcall!=NULL and rightcall!=NULL)  return root ;

      return root;
    }
};

输入

输出

迭代方法

使用双次遍历并分别找到节点 p 和 q 的路径，然后比较它们的路径以找到 LCA。

复杂度

时间复杂度

O(n)+O(n)

空间复杂度

O(n)+O(n)

打印 LCA 的函数

class Solution {
public:
//find path of both p and q 
bool findPath(TreeNode*root , vector<int>&path,TreeNode*toSearch){

    if(root==NULL){
        return 0;
    }
   
   //Always store current node when moving from one path to other later we will remove if coming back with false 
    path.push_back(root->val);
   
   //if found
     if(root->val == toSearch->val){
         return true;
     }

    //see if toSearch for is found in any path return true
   bool leftSearch =  findPath(root->left,path,toSearch);
   bool rightSearch =  findPath(root->right,path,toSearch);

   if(leftSearch==true || rightSearch==true){
         return true;
     }

    //return false and remove last added node 
    path.pop_back();
    return false;
}
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==NULL){
            return NULL;
        }
          TreeNode*node = root;
        vector<int>pathforp , pathforq ; 

        bool resultLeft = findPath(root,pathforp,p);
        bool resultRight =findPath(root,pathforq,q);
        
      //  for(auto it : pathforp) cout<<it<<" ";
      //  cout<<"\n";
       // for(auto itr : pathforq) cout<<itr<<" ";
      // cout<<"\n";

        //if any p or q not found 
        if(resultLeft == false || resultRight==false) {
            return NULL;
        }
   
        //else path is present  
        bool check = 0;
        for(int i=0; i<pathforp.size() and i<pathforq.size() ; i++){
              if(pathforp[i]!=pathforq[i]){
                  //i.e just previous value is answer 
                  node->val = pathforp[i-1];
                  check=1;
                    break;
                     }
        }
       if(!check){
           int mini = min(pathforp.size() , pathforq.size()) ;
         node->val = pathforp[mini-1]; //i.e both p and q were equal so return last value of smaller path as check=0
         /* [1,2] , p=2 , q=1
        pathforp ->  1 2 
        pathforq ->  1
        ans = 1
         */
       }  
        return node; //we can also return root
    }
};

输入

输出

用 Python 打印 LCA 的函数

class Solution:
    def lowestCommonAncestor(self, root, n1, n2):
        if root is None:
            return None

        if root.val == n1.val or root.val == n2.val:
            return root

        leftans = self.lowestCommonAncestor(root.left, n1, n2)
        rightans = self.lowestCommonAncestor(root.right, n1, n2)

        if leftans is not None and rightans is not None:
            return root
        elif leftans is not None:
            return leftans
        elif rightans is not None:
            return rightans
        else:
            return None

输入

输出

用 Java 打印 LCA 的函数

class Solution {
  public TreeNode lowestCommonAncestor(TreeNode root, TreeNode n1, TreeNode n2) {
    if (root == null || root == n1 || root == n2) {
      return root;
    }

    TreeNode leftans = lowestCommonAncestor(root.left, n1, n2);
    TreeNode rightans = lowestCommonAncestor(root.right, n1, n2);

    if (leftans != null && rightans != null) {
      return root;
    } else if (leftans != null) {
      return leftans;
    } else {
      return rightans;
    }
  }
}

输入

输出

下一主题二叉树的顶部视图

二叉树的最低公共祖先

二叉树的最低公共祖先代表什么？

LCA（最低公共祖先）的应用

示例

方法 -

C++ 程序

迭代方法

用 Python 打印 LCA 的函数

用 Java 打印 LCA 的函数

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

二叉树的最低公共祖先

二叉树的最低公共祖先代表什么？

LCA（最低公共祖先）的应用

示例

方法 -

C++ 程序

迭代方法

用 Python 打印 LCA 的函数

用 Java 打印 LCA 的函数

相关帖子

N 元树的直径

Java 中通过减去相等数量使数组变为零

展开链表

构建线性类型后缀

Golang 中的 AVL 树实现

双向链表上的快速排序

给定父数组时 N 元树的高度

提高密码强度

限制性糖果粉碎 - Javatpoint

用于范围顺序统计的归并排序树

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器