Ən aşağı ümumi əcdad

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Çiy kərpic Amazon alma Bloomberg Facebook google LinkedIn microsoft Kahin Pony.ai Zillow
AğacBaxılıb 72

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

İkilik kökü verilmişdir ağac və iki qovşaq n1 və n2, qovşaqların LCA (Ən aşağı ümumi ata) tapın.

misal

Ən aşağı ümumi əcdadPin

Ən aşağı ümumi əcdad (LCA) nədir?

Bir düyününün əcdadları kök və düyün arasındakı yolda olan qovşaqlardır. Yuxarıdakı nümunədə göstərilən ikili ağacı düşünün.
60-ın ataları 10, 30, 40 və 60-dır
50-nin ataları 10, 30 və 50-dir
N1 və n2-nin ən aşağı ortaq əcdadı iki düyünün ən aşağı (ikili ağacda) ortaq əcdadı və ya iki düyünün son ortaq əcdadıdır. Yəni 50 və 60 üçün LCA 30-dur.

Ən aşağı ümumi əcdad üçün sadəlövh yanaşma

N1 və n2 LCA,

  1. Kökdən n1-ə qədər yolu bir sıra path1-də tapın və saxlayın.
  2. Kökdən n2-yə gedən yolu başqa bir sıra 2-də tapın və saxlayın.
  3. Kökdən n1-ə gedən bir yol yoxdursa (kök n1 mövcud deyil) və ya kökdən n2-yə (n2 kök mövcud deyil) null qaytarın.
  4. Başqa iki yol dizisini müqayisə edin, LCA, yol massivlərindəki son ümumi qovşaqdır.

Yol alqoritmini tapın

Kökdən verilmiş düyünə bir yol varsa, yolu bir sıra içərisində saxla və true return return false qayıdın.

  1. Kök boşdursa, yalan qayıdır.
  2. Cari düyün tələb olunan düyündürsə, cari düyünü yol massivinə əlavə edin.
  3. Sol və sağ alt ağac üçün findPath funksiyasını təkrarən çağıraraq sol və sağ alt ağacdakı yolu yoxlayın.
  4. Sol və ya sağ alt ağacda bir yol varsa, doğru qayıdın.
  5. Başqa bir halda cari düyünü yol massivindən çıxarın və false qayıdın.

Ən aşağı ümumi əcdad üçün JAVA kodu

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);
    }
}

Ən aşağı ümumi əcdad üçün C ++ kodu

#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

Mürəkkəblik təhlili

Zaman Mürəkkəbliyi = O (n)
Yuxarıdakı həll tələb olunur 3 keçid ağacın ikisi, yol massivlərini doldurmaq üçün ikisi və bu massivləri müqayisə etmək üçün 1.

Ən aşağı ortaq əcdad üçün optimal yanaşma

LCA tapmaq məcburiyyətində olduğumuz n1 və n2-nin ağacda olduğunu düşünsək, yuxarıdakı problem tək keçidlə həll edilə bilər.

Ağacdan keçin, hər qovşaq üçün dörd haldan birinə sahibik,

  1. Mövcud node ya n1, ya da n2-dir, bu halda nodu qaytarırıq.
  2. Cari düyünün alt ağaclarından biri n1, digəri n2 ehtiva edir, bu düyün LCA-dır, düyünü qaytarın.
  3. Cari düyünün bir alt ağacı həm n1 həm də n2 ehtiva edir, alt ağacın qaytardığını qaytarırıq.
  4. Alt ağacların heç birində n1 və n2 yoxdur, return null.

Ən aşağı ümumi əcdad üçün JAVA kodu

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);
    }
}

Ən aşağı ümumi əcdad üçün C ++ kodu

#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

Mürəkkəblik təhlili

Zaman Mürəkkəbliyi = O (n) hara n verilmiş ağacda mövcud olan qovşaq sayıdır.
Yuxarıdakı həll a tələb edir tək keçid LCA tapmaq.

References

Crack Sistemi Dizayn Müsahibələri
Translate »