最低共同祖先


难度级别 中等
经常问 土砖 亚马逊 Apple 彭博 Facebook 谷歌 LinkedIn 微软 神谕 Pony.ai Zillow的

给定二进制的根 和两个节点n1和n2,找到节点的LCA(最低公共祖先)。

使用案列

最低共同祖先

什么是最低共同祖先(LCA)?

节点n的祖先是存在于根与节点之间的路径中的节点。 考虑上面示例中显示的二叉树。
60的祖先是10、30、40和60
50的祖先是10、30和50
n1和n2的最低公共祖先是两个节点的最低(在二叉树中)公共祖先,或者是两个节点的最后一个公共祖先。 也就是说,对于50和60,LCA为30。

最低共同祖先的幼稚方法

可以找到n1和n2的LCA为

  1. 在数组path1中找到从根到n1的路径并将其存储。
  2. 查找从根到n2的路径并将其存储在另一个数组path2中。
  3. 如果没有从根到n1(根n1不存在)或从根到n2(根n2不存在)的路径,则返回null。
  4. 否则比较两个路径数组,LCA是路径数组中的最后一个公共节点。

查找路径算法

如果存在从根到给定节点的路径,则将该路径存储在数组中并返回true,否则返回false。

  1. 如果root为null,则返回false。
  2. 如果当前节点是必需节点,则将当前节点添加到路径数组中,然后返回true。
  3. 通过递归调用左侧和右侧子树的findPath函数,检查左侧和右侧子树中的路径。
  4. 如果左子树或右子树中均存在路径,则返回true。
  5. 否则,从路径数组中删除当前节点,然后返回false。

最低共同祖先的JAVA代码

import java.util.*;

public class BinaryTreeLCA {
    // class to represent node of a binary tree
    static class Node {
        int data;
        Node left, right;

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

    private static Node LCA(Node root, int n1, int n2) {
        // Stores path from root to n1
        ArrayList<Node> path1 = new ArrayList<>();
        // Stores path from root to n2
        ArrayList<Node> path2 = new ArrayList<>();

        if (!findPath(root, n1, path1) || !findPath(root, n2, path2)) {
            // Either n1 or n2 does not exists in the tree
            return null;
        }

        // Compare the two path arrays
        Node LCA = null;
        for (int i = 0; i < path1.size() && i < path2.size(); i++) {
            if (path1.get(i) != path2.get(i)) {
                // First non common node
                break;
            } else {
                LCA = path1.get(i);
            }
        }
        return LCA;
    }

    // Function to find the path from root to given node and store it in an array
    private static boolean findPath(Node root, int n, ArrayList<Node> path) {
        if (root == null) {
            // Return false if root is null
            return false;
        }

        // Add the current root in the path array
        path.add(root);
        // If this node is the required node return true
        if (root.data == n) {
            return true;
        }

        // Find path in the left and right sub tree
        if (findPath(root.left, n, path) || findPath(root.right, n, path)) {
            // If there is a path in either left or right sub tree return true
            return true;
        }
        // Else remove root from path array and return false
        path.remove(root);
        return false;
    }

    public static void main(String[] args) {
        // Construct the tree shown in above example
        Node root = new Node(10);
        root.left = new Node(20);
        root.right = new Node(30);
        root.right.left = new Node(40);
        root.right.right = new Node(50);
        root.right.left.left = new Node(60);
        root.right.right.left = new Node(70);
        root.right.right.right = new Node(80);

        // Queries
        System.out.println(LCA(root, 20, 80).data);
        System.out.println(LCA(root, 80, 30).data);
        System.out.println(LCA(root, 70, 80).data);
    }
}

最低公祖的C ++代码

#include <iostream>
#include <vector>
using namespace std;

// Class representing node of binary 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 find the path from root to given node and store it in an array
bool findPath(Node *root, int n, vector<int> &path) {
    if (root == NULL) {
        // Return false if root is null
        return false;
    }
    
    // Add the current root in the path array
    path.push_back(root->data);
    // If this node is the required node return true
    if (root->data == n) {
        return true;
    }
    
    // Find path in the left and right sub tree
    if (findPath(root->left, n, path) || findPath(root->right, n, path)) {
        // If there is a path in either left or right sub tree return true
        return true;
    }
    // Else remove root from path array and return false
    path.pop_back();
    return false;
}

int LCA(Node *root, int n1, int n2) {
    // Stores path from root to n1
    vector<int> path1;
    // Stores path from root to n2
    vector<int> path2;
    
    if (!findPath(root, n1, path1) || !findPath(root, n2, path2)) {
        // Either n1 or n2 does not exists in the tree
        return -1;
    }
    
    // Compare the two path arrays
    int i = 0;
    for (; i < path1.size() && i < path2.size(); i++) {
        if (path1[i] != path2[i]) {
            // First non common node
            break;
        }
    }
    return path1[i - 1];
}

int main() {
  // Construct the tree shown in above example
    Node *root = newNode(10);
    root->left = newNode(20);
    root->right = newNode(30);
    root->right->left = newNode(40);
    root->right->right = newNode(50);
    root->right->left->left = newNode(60);
    root->right->right->left = newNode(70);
    root->right->right->right = newNode(80);
    
    // Queries
    cout<<LCA(root, 20, 80)<<endl;
    cout<<LCA(root, 80, 30)<<endl;
    cout<<LCA(root, 70, 80)<<endl;
    
    return 0;
}
10
30
50

复杂度分析

时间复杂度= O(N)
以上解决方案要求 3遍历 树中的1个,两个用于填充路径数组,XNUMX个用于比较这些数组。

最低共同祖先的优化方法

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

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

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

最低共同祖先的JAVA代码

import java.util.ArrayList;

public class Naive {
    // class to represent node of a binary tree
    static class Node {
        int data;
        Node left, right;

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

    private static Node LCA(Node root, int n1, int n2) {
        // Stores path from root to n1
        ArrayList<Node> path1 = new ArrayList<>();
        // Stores path from root to n2
        ArrayList<Node> path2 = new ArrayList<>();

        if (!findPath(root, n1, path1) || !findPath(root, n2, path2)) {
            // Either n1 or n2 does not exists in the tree
            return null;
        }

        // Compare the two path arrays
        Node LCA = null;
        for (int i = 0; i < path1.size() && i < path2.size(); i++) {
            if (path1.get(i) != path2.get(i)) {
                // First non common node
                break;
            } else {
                LCA = path1.get(i);
            }
        }
        return LCA;
    }

    // Function to find the path from root to given node and store it in an array
    private static boolean findPath(Node root, int n, ArrayList<Node> path) {
        if (root == null) {
            // Return false if root is null
            return false;
        }

        // Add the current root in the path array
        path.add(root);
        // If this node is the required node return true
        if (root.data == n) {
            return true;
        }

        // Find path in the left and right sub tree
        if (findPath(root.left, n, path) || findPath(root.right, n, path)) {
            // If there is a path in either left or right sub tree return true
            return true;
        }
        // Else remove root from path array and return false
        path.remove(root);
        return false;
    }

    public static void main(String[] args) {
        // Construct the tree shown in above example
        Node root = new Node(10);
        root.left = new Node(20);
        root.right = new Node(30);
        root.right.left = new Node(40);
        root.right.right = new Node(50);
        root.right.left.left = new Node(60);
        root.right.right.left = new Node(70);
        root.right.right.right = new Node(80);

            // Queries
        System.out.println(LCA(root, 20, 80).data);
        System.out.println(LCA(root, 80, 30).data);
        System.out.println(LCA(root, 70, 80).data);
    }
}

最低公祖的C ++代码

#include <iostream>
#include <vector>
using namespace std;

// Class representing node of binary 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); 
}

Node* LCA(Node *root, int n1, int n2) {
    // Return null for a null root
    if (root == NULL) {
        return NULL;
    }
    
    // Current node is either n1 or n2
    if (root->data == n1 || root->data == n2) {
        return root;
    }
    
    // Traverse the tree to find the LCA in left and right sub tree
    Node *LCA1 = LCA(root->left, n1, n2);
    Node *LCA2 = LCA(root->right, n1, n2);
    
    // One of the sub tree contains n1 and other contains n2, this is the LCA
    if (LCA1 != NULL && LCA2 != NULL) {
        return root;
    }
    // Left sub tree contains both n1 and n2, return what sub tree returns
    if (LCA1 != NULL) {
        return LCA1;
    }
    // Right sub tree contains both n1 and n2, return what sub tree returns
    if (LCA2 != NULL) {
        return LCA2;
    }
    // None of the sub tree contains n1 and n2
    return NULL;
}

int main() {
  // Construct the tree shown in above example
    Node *root = newNode(10);
    root->left = newNode(20);
    root->right = newNode(30);
    root->right->left = newNode(40);
    root->right->right = newNode(50);
    root->right->left->left = newNode(60);
    root->right->right->left = newNode(70);
    root->right->right->right = newNode(80);
    
    // Queries
    cout<<LCA(root, 20, 80)->data<<endl;
    cout<<LCA(root, 80, 30)->data<<endl;
    cout<<LCA(root, 70, 80)->data<<endl;
    
    return 0;
}
10
30
50

复杂度分析

时间复杂度= O(N) 哪里 n 是给定树中存在的节点数。
上述解决方案需要 单遍历 查找LCA。

參考資料