二进制搜索树中的最低共同祖先


难度级别 易得奖学金
经常问 亚马逊 Facebook LinkedIn 神谕
二进制搜索树 二叉树 穿越 树遍历

给定二分查找的根 以及两个节点n1和n2,在给定的二叉搜索树中找到节点的LCA(最低公共祖先)。

使用案列

二进制搜索树中的最低共同祖先

二叉搜索树中最低共同祖先的朴素方法

使用最佳方法找到LCA(n1,n2),以在其中找到LCA 二叉树,因为BST也是二叉树。

如果我们假设必须在其中找到LCA的n1和n2存在于树中,则可以通过一次遍历来解决上述问题。

遍历树,对于每个节点,我们有以下四种情况之一:

  1. 当前节点是n1或n2,在这种情况下,我们返回该节点。
  2. 当前节点的一个子树包含n1,另一个包含n2,此节点为LCA,返回该节点。
  3. 当前节点的一个子树包含n1和n2,我们返回该子树返回的内容。
  4. 没有一个子树包含n1和n2,返回null。

时间复杂度= O(n),单遍历 
其中n是树中的节点数。

二叉搜索树中最小公祖的最优方法

使用BST的属性,可以发现LCA的时间复杂度要低得多。

  1. 从根开始遍历BST(将根初始化为curr)。
  2. 如果当前节点的值在n1和n2(包括两端)之间,则为LCA。
  3. 否则,如果节点的值小于n1和n2,则LCA出现在右半部分(curr变为curr.right)。
  4. 左半部分中存在其他LCA(curr变为curr.left)。

说明

考虑上图中的BST,让我们找到LCA(32,40)

从根开始遍历树。

  • 当前节点的值= 20
    20 <32和20 <40,LCA存在于右子树中
  • 当前节点的值= 24
    24 <32和20 <40,LCA位于右下方
  • 当前节点的值= 35
    35> = 32和35 <= 40,所以这是LCA
    即, LCA(32,40)= 35

二进制搜索树中最低公共祖先的JAVA代码

public class LCABST {
    // Class to represent a node in BST
    static class Node {
        int data;
        Node left, right;

        public Node(int data) {
            this.data = data;
            left = right = null;
        }
    }

    // Function to return LCA of two nodes, and return -1 if LCA does not exist
    private static int LCA(Node root, int n1, int n2) {
        // No LCA for an empty tree
        if (root == null) {
            return -1;
        }

        // Traverse the tree starting from root
        Node curr = root;
        int lca = -1;
        while (curr != null) {
            if (curr.data < n1 && curr.data < n2) {
                // LCA is present in the right sub tree
                curr = curr.right;
            } else if (curr.data > n1 && curr.data > n2) {
                // LCA is present in left sub tree
                curr = curr.left;
            } else {
                lca = curr.data;
                break;
            }
        }

        // Return LCA
        return lca;
    }

    public static void main(String[] args) {
        // Constructing the BST in above example
        Node root = new Node(20);
        root.left = new Node(11);
        root.right = new Node(24);
        root.right.left = new Node(21);
        root.right.right = new Node(35);
        root.right.right.left = new Node(32);
        root.right.right.right = new Node(40);

        // Queries
        System.out.println(LCA(root, 24, 40));
        System.out.println(LCA(root, 11, 21));
        System.out.println(LCA(root, 32, 40));
    }
}

二进制搜索树中最低公祖的C ++代码

#include <iostream>
using namespace std;

// Class representing node of binary search tree
class Node {
    public:
    int data;
    Node *left;
    Node *right;
};

// Function to allocate new memory to a tree node
Node* newNode(int data) { 
    Node *node = new Node(); 
    node->data = data; 
    node->left = NULL; 
    node->right = NULL;
  
    return (node); 
}

// Function to return LCA of two nodes, and return -1 if LCA does not exist
int LCA(Node *root, int n1, int n2) {
    // No LCA for an empty tree
    if (root == NULL) {
        return -1;
    }
    
    // Traverse the tree starting from root
    Node *curr = root;
    int lca = -1;
    while (curr != NULL) {
        if (curr->data < n1 && curr->data < n2) {
            // LCA is present in the right sub tree
            curr = curr->right;
        } else if (curr->data > n1 && curr->data > n2) {
            // LCA is present in left sub tree
            curr = curr->left;
        } else {
            lca = curr->data;
            break;
        }
    }
    
    // Return LCA
    return lca;
}

int main() {
  // Construct the tree shown in above example
    Node *root = newNode(20);
    root->left = newNode(11);
    root->right = newNode(24);
    root->right->left = newNode(21);
    root->right->right = newNode(35);
    root->right->right->left = newNode(32);
    root->right->right->right = newNode(40);
    
    // Queries
    cout<<LCA(root, 24, 40)<<endl;
    cout<<LCA(root, 11, 21)<<endl;
    cout<<LCA(root, 32, 40)<<endl;
    
    return 0;
}
24
20
35

复杂度分析

时间复杂度= 哦), 其中h是BST的高度

參考資料