Tìm tổ tiên chung thấp nhất trong Cây nhị phân (phần 1)

chia sẻ 14/12/2021| 275
  • Mức độ khó: Trung bình

Cho một cây nhị phân (không phải cây tìm kiếm nhị phân) và hai giá trị được gọi là n1 và n2, viết chương trình để tìm LCA (Least common ancestor).

 

Định nghĩa về LCA trên Wikipedia

Cho T là một cây có rễ, vậy Tổ tiên chung thấp nhất giữa 2 nút n1 và n2 được xác định như nút thấp nhất trong T và nhận n1 và n2 là con cháu (cho phép nút là con cháu của chính nó).

LCA của n1 và n2 trong T là tổ tiên chung của n1 và n1 được đặt xa gốc nhất. Ví dụ, việc tính toán tổ tiên chung thấp nhất có thể hữu ích như một phần của quy trình xác định khoảng cách giữa các cặp nút trong cây: khoảng cách từ n1 đến n2 có thể được tính bằng tổng khoảng cách từ gốc đến n1 và khoảng cách từ gốc đến n2 trừ đi 2 lần khoảng cách từ gốc đến tổ tiên chung thấp nhất.

 


Hãy thử giải Bài tập này trước khi chuyển đến phần giải pháp:

Cho cây nhị phân với các giá trị riêng biệt và hai nút giá trị n1 và n2. Hãy tìm tổ tiên chung thấp nhất của hai nút đã cho. Bạn có thể giả định rằng cả hai giá trị đều hiện diện trong cây hoặc không.

 Ví dụ 1: Ví dụ 2
Input:

n1 = 2 , n2 =  3

1

/   \

2    3

Output: 1

Explanation:

LCA of 2 and 3 is 1.

Input:

n1 = 3 , n2 = 4

5

/

2

/   \

3    4

Output: 2

Explanation:

LCA of 3 and 4 is 2.

Bạn cần hoàn thành hàm lca () lấy các nút, n1 và n2 làm tham số và trả về nút LCA làm output. Ngược lại, trả về một nút có giá trị -1 nếu cả n1 và n2 không có trong cây.

Độ phức tạp về thời gian: O (N).

Không gian phụ trợ: O (Chiều cao của cây).

Hạn chế:

1 ≤ Số lượng nút ≤ 105

1 ≤ Dữ liệu của một nút ≤ 105///


 

Trong Cây tìm kiếm nhị phân, sử dụng thuộc tính BST, chúng ta có thể tìm LCA trong thời gian O(h) trong đó h là chiều cao của cây. Không thể triển khai như vậy trong Cây nhị phân vì khóa các nút của Cây nhị phân không tuân theo bất kỳ thứ tự nào. Sau đây là các cách tiếp cận khác nhau để tìm LCA trong Cây nhị phân.

 

Phương pháp 1 (Bằng cách lưu trữ các đường dẫn từ gốc đến n1 và gốc tới n2):

Sau đây là một thuật toán O (n) đơn giản để tìm LCA của n1 và n2.

1) Tìm một đường dẫn từ gốc đến n1 và lưu trữ nó trong một vectơ hoặc mảng.

2) Tìm một đường dẫn từ gốc đến n2 và lưu trữ nó trong một vectơ hoặc mảng khác.

3) Di chuyển cả hai đường dẫn cho đến khi các giá trị trong mảng giống nhau. Trả lại phần tử chung ngay trước phần tử không khớp.

Sau đây là cách triển khai thuật toán trên:

C++

/* C++ Program to find LCA of n1 and n2 using one traversal of Binary Tree */
#include

using namespace std;

// A Binary Tree Node
struct Node
{
struct Node *left, *right;
int key;
};

// Utility function to create a new tree Node
Node* newNode(int key)
{
Node *temp = new Node;
temp->key = key;
temp->left = temp->right = NULL;
return temp;
}

// This function returns pointer to LCA of two given values n1 and n2.
// This function assumes that n1 and n2 are present in Binary Tree
struct Node *findLCA(struct Node* root, int n1, int n2)
{
// Base case
if (root == NULL) return NULL;

// If either n1 or n2 matches with root's key, report
// the presence by returning root (Note that if a key is
// ancestor of other, then the ancestor key becomes LCA
if (root->key == n1 || root->key == n2)
return root;

// Look for keys in left and right subtrees
Node *left_lca = findLCA(root->left, n1, n2);
Node *right_lca = findLCA(root->right, n1, n2);

// If both of the above calls return Non-NULL, then one key
// is present in once subtree and other is present in other,
// So this node is the LCA
if (left_lca && right_lca) return root;

// Otherwise check if left subtree or right subtree is LCA
return (left_lca != NULL)? left_lca: right_lca;
}

// Driver program to test above functions
int main()
{
// Let us create binary tree given in the above example
Node * root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(6);
root->right->right = newNode(7);
cout << "LCA(4, 5) = " << findLCA(root, 4, 5)->key;
cout << "nLCA(4, 6) = " << findLCA(root, 4, 6)->key;
cout << "nLCA(3, 4) = " << findLCA(root, 3, 4)->key;
cout << "nLCA(2, 4) = " << findLCA(root, 2, 4)->key;
return 0;
}

Java
//Java implementation to find lowest common ancestor of
// n1 and n2 using one traversal of binary tree

/* Class containing left and right child of current
node and key value*/
class Node
{
int data;
Node left, right;

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

public class BinaryTree
{
//Root of the Binary Tree
Node root;

Node findLCA(int n1, int n2)
{
return findLCA(root, n1, n2);
}

// This function returns pointer to LCA of two given
// values n1 and n2. This function assumes that n1 and
// n2 are present in Binary Tree
Node findLCA(Node node, int n1, int n2)
{
// Base case
if (node == null)
return null;

// If either n1 or n2 matches with root's key, report
// the presence by returning root (Note that if a key is
// ancestor of other, then the ancestor key becomes LCA
if (node.data == n1 || node.data == n2)
return node;

// Look for keys in left and right subtrees
Node left_lca = findLCA(node.left, n1, n2);
Node right_lca = findLCA(node.right, n1, n2);

// If both of the above calls return Non-NULL, then one key
// is present in once subtree and other is present in other,
// So this node is the LCA
if (left_lca!=null && right_lca!=null)
return node;

// Otherwise check if left subtree or right subtree is LCA
return (left_lca != null) ? left_lca : right_lca;
}

/* Driver program to test above functions */
public static void main(String args[])
{
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
tree.root.right.left = new Node(6);
tree.root.right.right = new Node(7);
System.out.println("LCA(4, 5) = " +
tree.findLCA(4, 5).data);
System.out.println("LCA(4, 6) = " +
tree.findLCA(4, 6).data);
System.out.println("LCA(3, 4) = " +
tree.findLCA(3, 4).data);
System.out.println("LCA(2, 4) = " +
tree.findLCA(2, 4).data);
}
}

Python
# Python program to find LCA of n1 and n2 using one
# traversal of Binary tree

# A binary tree node
class Node:

# Constructor to create a new tree node
def __init__(self, key):
self.key = key
self.left = None
self.right = None

# This function returns pointer to LCA of two given
# values n1 and n2
# This function assumes that n1 and n2 are present in
# Binary Tree
def findLCA(root, n1, n2):

# Base Case
if root is None:
return None

# If either n1 or n2 matches with root's key, report
# the presence by returning root (Note that if a key is
# ancestor of other, then the ancestor key becomes LCA
if root.key == n1 or root.key == n2:
return root

# Look for keys in left and right subtrees
left_lca = findLCA(root.left, n1, n2)
right_lca = findLCA(root.right, n1, n2)

# If both of the above calls return Non-NULL, then one key
# is present in once subtree and other is present in other,
# So this node is the LCA
if left_lca and right_lca:
return root

# Otherwise check if left subtree or right subtree is LCA
return left_lca if left_lca is not None else right_lca

# Driver program to test above function

# Let us create a binary tree given in the above example
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
print "LCA(4,5) = ", findLCA(root, 4, 5).key
print "LCA(4,6) = ", findLCA(root, 4, 6).key
print "LCA(3,4) = ", findLCA(root, 3, 4).key
print "LCA(2,4) = ", findLCA(root, 2, 4).key

# This code is contributed by Nikhil Kumar Singh(nickzuck_007)

C#
// C# implementation to find lowest common
// ancestor of n1 and n2 using one traversal
// of binary tree
using System;

// Class containing left and right
// child of current node and key value
public class Node
{
public int data;
public Node left, right;

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

class BinaryTree{

// Root of the Binary Tree
Node root;

Node findLCA(int n1, int n2)
{
return findLCA(root, n1, n2);
}

// This function returns pointer to LCA
// of two given values n1 and n2. This
// function assumes that n1 and n2 are
// present in Binary Tree
Node findLCA(Node node, int n1, int n2)
{

// Base case
if (node == null)
return null;

// If either n1 or n2 matches with
// root's key, report the presence
// by returning root (Note that if
// a key is ancestor of other,
// then the ancestor key becomes LCA
if (node.data == n1 || node.data == n2)
return node;

// Look for keys in left and right subtrees
Node left_lca = findLCA(node.left, n1, n2);
Node right_lca = findLCA(node.right, n1, n2);

// If both of the above calls return Non-NULL,
// then one key is present in once subtree
// and other is present in other, So this
// node is the LCA
if (left_lca != null && right_lca != null)
return node;

// Otherwise check if left subtree or
// right subtree is LCA
return (left_lca != null) ? left_lca : right_lca;
}

// Driver code
public static void Main(string []args)
{
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
tree.root.right.left = new Node(6);
tree.root.right.right = new Node(7);

Console.WriteLine("LCA(4, 5) = " +
tree.findLCA(4, 5).data);
Console.WriteLine("LCA(4, 6) = " +
tree.findLCA(4, 6).data);
Console.WriteLine("LCA(3, 4) = " +
tree.findLCA(3, 4).data);
Console.WriteLine("LCA(2, 4) = " +
tree.findLCA(2, 4).data);
}
}

// This code is contributed by pratham76

Javascript

// JavaScript implementation to find
// lowest common ancestor of
// n1 and n2 using one traversal of binary tree

class Node
{
constructor(item) {
this.left = null;
this.right = null;
this.data = item;
}
}

//Root of the Binary Tree
let root;

function findlCA(n1, n2)
{
return findLCA(root, n1, n2);
}

// This function returns pointer to LCA of two given
// values n1 and n2. This function assumes that n1 and
// n2 are present in Binary Tree
function findLCA(node, n1, n2)
{
// Base case
if (node == null)
return null;

// If either n1 or n2 matches with root's key, report
// the presence by returning root (Note that if a key is
// ancestor of other, then the ancestor key becomes LCA
if (node.data == n1 || node.data == n2)
return node;

// Look for keys in left and right subtrees
let left_lca = findLCA(node.left, n1, n2);
let right_lca = findLCA(node.right, n1, n2);

// If both of the above calls return Non-NULL, then one key
// is present in once subtree and other is present in other,
// So this node is the LCA
if (left_lca!=null && right_lca!=null)
return node;

// Otherwise check if left subtree or right subtree is LCA
return (left_lca != null) ? left_lca : right_lca;
}

root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
document.write("LCA(4, 5) = " +
findlCA(4, 5).data + "
");
document.write("LCA(4, 6) = " +
findlCA(4, 6).data + "
");
document.write("LCA(3, 4) = " +
findlCA(3, 4).data + "
");
document.write("LCA(2, 4) = " +
findlCA(2, 4).data + "
");

Output:
LCA(4, 5) = 2
LCA(4, 6) = 1
LCA(3, 4) = 1
LCA(2, 4) = 2

Độ phức tạp về thời gian: Độ phức tạp về thời gian trong giải pháp trên là O(n). Cây được dịch chuyển 2 lần và sau đó được so sánh với các mảng đường dẫn.
Giải pháp này đã được đề xuất bởi Ravi Chandra Enaganti dựa trên phương pháp này.


Đăng trong Kiến thức IT, Tin tức Công nghệ, Uncategorized chia sẻ

Tin tức khác

Top 10 lợi ích của chứng chỉ AWS Certificate

Hiện nay, điện toán đám mây (cloud computing) đang là xu hướng mới nhất trong ngành Công nghệ thông tin. Mọi tổ chức, dù lớn hay ...

Xem thêm

Từng bước xây dựng thành công khi làm việc tại Nhật – Xử lý tình huống khi chuyển việc tại Nhật?

Tìm việc tại Nhật không phải là chuyện đơn giản, và chuyển việc tại Nhật cũng là kéo theo khá nhiều vấn đề phát sinh, nhất ...

Xem thêm

Từng bước xây dựng thành công khi làm việc tại Nhật – Thế nào là một công việc tiềm năng?

Tiếp nối chuỗi bài viết mang tên “Từng bước xây dựng thành công khi làm việc tại Nhật” gồm 14 bài, tổng hợp toàn bộ những ...

Xem thêm

Từng bước xây dựng thành công khi làm việc tại Nhật – Làm sao để chuyển việc?

CO-WELL Will & Way đã quay trở lại, mang đến bạn bài viết thứ 3 trong chuỗi “Từng bước xây dựng thành công khi làm việc tại ...

Xem thêm