가장 낮은 공통 조상

난이도 중급
자주 묻는 질문 어도비 벽돌 아마존 Apple 블룸버그 게시물에서 Facebook 구글 링크드인 Microsoft 신탁 조랑말 Zillow
나무조회수 73

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

링크드인버퍼레딧텀블러

바이너리의 루트가 주어지면 나무 두 개의 노드 n1과 n2는 노드의 LCA (Lowest Common Ancestor)를 찾습니다.

예

가장 낮은 공통 조상핀

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. 루트가 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 개는이 배열을 비교합니다.

최하위 공통 조상을위한 최적화 된 접근 방식

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를 찾으십시오.

참조

링크드인버퍼레딧텀블러
균열 시스템 설계 인터뷰
Translate »