二叉搜索树中的最低公共祖先

17 Mar 2025 | 4 分钟阅读

二叉搜索树

二叉搜索树是一种二叉树，其中任何节点的所有小于它的值都存在于其左子树中，而所有大于它的值都存在于其右子树中。

问题陈述

我们给出了二叉搜索树的根节点以及两个整数值 n 和 m。我们的任务是返回二叉搜索树中这两个节点的最低公共祖先。

例如

Lowest Common Ancestor in a Binary Search Tree

在上例中，我们有一棵二叉搜索树，我们将找出一些节点的最低公共祖先。

n=6，m=15，则最低公共祖先是 12
n=4，m=22，则最低公共祖先是 12
n=7，m=9，则最低公共祖先是 9

方法 1

我们将找出从根节点到节点 1 的路径和从根节点到节点 2 的路径，并将其存储在 ArrayList 中。现在，ArrayList 的第一个公共元素将是最低公共祖先。

Java 代码

import java.util.*;
public class Main {
//creating the node for the tree
    public static class Node{
        int data;
        Node left;
        Node right;
        Node(int data){
            this.data=data;
            this.left=null;
            this.right=null;
        }
    }
  public static void main(String[] args) {
        Node root= new Node(12);
        root.left=new Node(6);
        root.right=new Node(15);
        root.left.left=new Node(4);
        root.left.right=new Node(9);
        root.left.right.left=new Node(7);
        root.left.right.right=new Node(11);
        root.right.right=new Node(22);
        
        int node1 = 7;
        int node2 = 22;
        ArrayList<Integer> list1 = new ArrayList<>();
        ArrayList<Integer> list2 = new ArrayList<>();
        rootToNodePath(root,node1,list1);
        rootToNodePath(root,node2,list2);
        int p1=0;
        int p2=0;
        if(list1.size()>list2.size()){
            p1+=list1.size()-list2.size();
        }else{
            p2+=list2.size()-list1.size();
        }
        while(p1< list1.size() && p2<list2.size()){
            if(list1.get(p1)==list2.get(p2))
            break;
            p1++;
            p2++;
        }
        System.out.println("lowest common ancestor of node "+node1+" node "+node2+" is "+list1.get(p1));
  }
  public static void rootToNodePath(Node root,int node,ArrayList<Integer> list){
      list.add(0,root.data);
      if(root.data==node)
      return;
      if(root.data<node)
      rootToNodePath(root.right,node,list);
      else
      rootToNodePath(root.left,node,list);
  }
}

输出

时间复杂度： O(H)+O(H)，其中 H 是树的高度。在最坏的情况下，它可以高达 O(N)。

空间复杂度： 最坏情况下为 O(N)+O(N)。

方法 2

我们将使用递归来获得节点的最低公共祖先。

在递归调用中，如果当前节点等于节点 1 或节点 2，则当前节点将是 LCS（最低公共祖先）。
如果当前节点的值小于一个节点且大于另一个节点，则当前节点将是 LCS。
如果当前节点的值小于两个节点的值，则答案将位于当前节点的右子树中。
如果当前节点的值大于两个节点的值，则答案将位于当前节点的左子树中。

Java 代码

import java.util.*;
public class Main {
//creating the node for the tree
    public static class Node{
        int data;
        Node left;
        Node right;
        Node(int data){
            this.data=data;
            this.left=null;
            this.right=null;
        }
    }
  public static void main(String[] args) {
        Node root= new Node(12);
        root.left=new Node(6);
        root.right=new Node(15);
        root.left.left=new Node(4);
        root.left.right=new Node(9);
        root.left.right.left=new Node(7);
        root.left.right.right=new Node(11);
        root.right.right=new Node(22);
        
        int node1 = 4;
        int node2 = 11;
        int answer = getLowestCommonAncestor(root,node1,node2);
        System.out.println("lowest common ancestor of node "+node1+" node "+node2+" is "+answer);
  }
  public static int getLowestCommonAncestor(Node currentNode,int node1,int node2){
     if(currentNode.data==node1 || currentNode.data==node2){
         return currentNode.data;
     }
     
     if((currentNode.data<node1 && currentNode.data>node2)||(currentNode.data<node2 && currentNode.data>node1)){
         return currentNode.data;
     }
     
     if(currentNode.data<node1 && currentNode.data<node2){
         return getLowestCommonAncestor(currentNode.right,node1,node2);
     }
     
     if(currentNode.data>node1 && currentNode.data>node2){
         return getLowestCommonAncestor(currentNode.left,node1,node2);
     }
     return -1;
  }
}

输出

时间复杂度：最坏情况下为 O(N)；否则为 O(H)，其中 H 是高度。

空间复杂度：O(H) 辅助递归栈空间。

方法 3

此方法是上述解决方案的迭代方法。它将帮助我们节省递归占用的辅助堆栈空间。

Java 代码

import java.util.*;
public class Main {
//creating the node for the tree
    public static class Node{
        int data;
        Node left;
        Node right;
        Node(int data){
            this.data=data;
            this.left=null;
            this.right=null;
        }
    }
  public static void main(String[] args) {
        Node root= new Node(12);
        root.left=new Node(6);
        root.right=new Node(15);
        root.left.left=new Node(4);
        root.left.right=new Node(9);
        root.left.right.left=new Node(7);
        root.left.right.right=new Node(11);
        root.right.right=new Node(22);
        
        int node1 = 7;
        int node2 = 15;
        int answer=-1;
        Node currentNode = root;
        while(currentNode!=null){
            if(currentNode.data==node1 || currentNode.data==node2){
                 answer = currentNode.data;
                 break;
            }
            if((currentNode.data<node1 && currentNode.data>node2)||(currentNode.data<node2 && currentNode.data>node1)){
                 answer = currentNode.data;
                 break;
            }
            if(currentNode.data<node1 && currentNode.data<node2){
                currentNode=currentNode.right;
            }
            if(currentNode.data>node1 && currentNode.data>node2){
                currentNode=currentNode.left;
            }
        }
        System.out.println("lowest common ancestor of node "+node1+" node "+node2+"  is "+answer);
  }

}

输出

时间复杂度： O(H)，其中 H 是树的高度，在最坏的情况下可以是 N。

空间复杂度： O(1)，因为不使用辅助空间。

下一个主题C 语言中的哈希函数类型

二叉搜索树中的最低公共祖先