ບັນພະບຸລຸດ ທຳ ມະດາທີ່ຕໍ່າທີ່ສຸດ


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ Adobe Amazon ຈາກຫນາກແອບເປີ Bloomberg ເຟສບຸກ ກູໂກ LinkedIn Microsoft Oracle Pony.ai Zillow
ຕົ້ນໄມ້

ໃຫ້ຮາກຂອງຖານສອງ ເປັນໄມ້ຢືນຕົ້ນ ແລະສອງຂໍ້ n1 ແລະ n2, ຊອກຫາ LCA (ບັນພະບຸລຸດຄົນ ທຳ ມະດາຕ່ ຳ ສຸດ) ຂອງຂໍ້.

ຍົກຕົວຢ່າງ

ບັນພະບຸລຸດ ທຳ ມະດາທີ່ຕໍ່າທີ່ສຸດ

ບັນພະບຸລຸດສາມັນຕ່ ຳ ທີ່ສຸດ (LCA) ແມ່ນຫຍັງ?

ບັນພະບຸລຸດຂອງ node n ແມ່ນຂໍ້ທີ່ຢູ່ໃນເສັ້ນທາງລະຫວ່າງຮາກແລະຂໍ້. ພິຈາລະນາຕົ້ນໄມ້ຖານສອງທີ່ສະແດງຢູ່ໃນຕົວຢ່າງຂ້າງເທິງ.
ບັນພະບຸລຸດຂອງ 60 ແມ່ນ 10, 30, 40 ແລະ 60
ບັນພະບຸລຸດ 50 ປີແມ່ນ 10, 30 ແລະ 50
ບັນດາບັນພະບຸລຸດ ທຳ ມະດາທີ່ຕໍ່າທີ່ສຸດຂອງ n1 ແລະ n2 ແມ່ນຊັ້ນລຸ່ມທີ່ສຸດ (ໃນຕົ້ນໄມ້ຖານສອງ) ນັ້ນແມ່ນ, ສໍາລັບ 50 ແລະ 60 LCA ແມ່ນ 30.

ວິທີການ Naive ສຳ ລັບບັນພະບຸລຸດ ທຳ ມະດາທີ່ຕໍ່າທີ່ສຸດ

LCA ຂອງ n1 ແລະ n2 ສາມາດພົບໄດ້,

  1. ຊອກຫາແລະເກັບຮັກສາເສັ້ນທາງຈາກຮາກຫາ n1 ໃນແຖວ path1.
  2. ຊອກຫາແລະເກັບມ້ຽນເສັ້ນທາງຈາກຮາກຫາ n2 ໃນອີກເສັ້ນ ໜຶ່ງ array.
  3. ຖ້າບໍ່ມີເສັ້ນທາງຈາກຮາກຫາ n1 (ຮາກ n1 ບໍ່ມີ) ຫຼືຈາກຮາກຫາ n2 (ຮາກ n2 ບໍ່ມີ) ກັບຄືນ null.
  4. ອື່ນປຽບທຽບສອງເສັ້ນທາງເສັ້ນທາງ, LCA ແມ່ນຂໍ້ທີ່ພົບກັນສຸດທ້າຍໃນເສັ້ນທາງເສັ້ນທາງ.

ຊອກຫາເສັ້ນທາງ Algorithm

ຖ້າຫາກວ່າເສັ້ນທາງຈາກຮາກຫາຂໍ້ທີ່ໃຫ້ໄວ້ມີຢູ່, ເກັບເສັ້ນທາງນັ້ນເປັນແຖວແລະສົ່ງຄືນອີກອັນ ໜຶ່ງ ທີ່ບໍ່ຖືກຕ້ອງ.

  1. ຖ້າຮາກແມ່ນ null ກັບຄືນບໍ່ຖືກຕ້ອງ.
  2. ຕື່ມໃສ່ node ປັດຈຸບັນຢູ່ໃນ array path, ຖ້າ node ປັດຈຸບັນແມ່ນ node ທີ່ຕ້ອງການກັບຄືນມາເປັນຄວາມຈິງ.
  3. ກວດເບິ່ງເສັ້ນທາງໃນລັດຖະບັນຍັດຊ້າຍແລະຂວາໂດຍການໂທຫາການຄົ້ນຫາຄືນ ໃໝ່ ສຳ ລັບ ໜ້າ ທີ່ຄົ້ນຫາເບື້ອງຊ້າຍແລະຂວາ.
  4. ຖ້າມີເສັ້ນທາງໃນລັດຖະບັນຍັດຊ້າຍຫລືຂວາ, ໃຫ້ກັບມາເປັນຄວາມຈິງ.
  5. ອື່ນເອົາ node ປັດຈຸບັນອອກຈາກຂບວນເສັ້ນທາງແລະສົ່ງຄືນທີ່ບໍ່ຖືກຕ້ອງ.

ລະຫັດ 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 ເພື່ອປຽບທຽບບັນດາຂບວນເຫຼົ່ານີ້.

ວິທີການທີ່ດີທີ່ສຸດ ສຳ ລັບບັນພະບຸລຸດ ທຳ ມະດາທີ່ຕໍ່າທີ່ສຸດ

ຖ້າພວກເຮົາສົມມຸດວ່າ n1 ແລະ n2, ເຊິ່ງພວກເຮົາຕ້ອງຊອກຫາ LCA, ມີຢູ່ໃນຕົ້ນໄມ້, ບັນຫາຂ້າງເທິງນີ້ສາມາດແກ້ໄຂໄດ້ໃນທາງດຽວ.

ຂ້າມຕົ້ນໄມ້, ສຳ ລັບທຸກໆ node ພວກເຮົາມີ ໜຶ່ງ ໃນສີ່ກໍລະນີ,

  1. node ປະຈຸບັນແມ່ນ n1 ຫຼື n2, ໃນກໍລະນີນີ້, ພວກເຮົາສົ່ງຄືນ node.
  2. ໜຶ່ງ ໃນບັນດາຂໍ້ຍ່ອຍຂອງ node ປັດຈຸບັນມີ n1 ແລະອີກ ໜຶ່ງ ປະກອບດ້ວຍ n2, node ນີ້ແມ່ນ LCA, ສົ່ງຄືນ node.
  3. ໜຶ່ງ ໃນລັດຖະບັນຍັດຂອງ node ປັດຈຸບັນມີທັງ n1 ແລະ n2, ພວກເຮົາສົ່ງຄືນສິ່ງທີ່ອະນຸ ກຳ ມະການຈະກັບມາ.
  4. ບໍ່ມີບົດບັນຍັດໃດປະກອບມີ n1 ແລະ n2, ບໍ່ສົ່ງຄືນ.

ລະຫັດ 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 ແມ່ນ ຈຳ ນວນຂອງຂໍ້ທີ່ຢູ່ໃນຕົ້ນໄມ້ທີ່ໃຫ້.
ການແກ້ໄຂຂ້າງເທິງນີ້ຮຽກຮ້ອງໃຫ້ມີ traversal ດຽວ ເພື່ອຊອກຫາ LCA.

ເອກະສານ