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

chia sẻ 14/12/2021| 246
  • 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 8 blog IT hay nhất dành cho bạn khi bước vào nghề lập trình

“Đi một ngày đàng, học một sàng khôn”. Đôi khi để học tốt không có nghĩa là bạn cứ luôn phải cắm mặt vào sách vở ...

Xem thêm

Xu hướng Công nghệ 2022: Điều gì sẽ là một “cú nổ lớn”?

Công nghệ không ngừng thay đổi, việc các công nghệ mới xuất hiện từng ngày khiến cho việc dự đoán những Xu hướng Công nghệ 2020 ...

Xem thêm

Mùa lá thu đã điểm – ngắm lá đỏ ở Nhật 2021 nơi nào đẹp nhất?

Giống như tháng 4 với màu hồng xinh xắn của hoa anh đào – sakura, từ tháng mười cho đến tháng 12 cũng là thời điểm ...

Xem thêm

Top 8 kênh Youtube về lập trình hàng đầu mà bạn không thể bỏ lỡ

YouTube là một nguồn tài nguyên tuyệt vời để học các kỹ năng mới và trau dồi thêm những kiến thức hiện có. Nhưng đôi lúc ...

Xem thêm