Cho cây nhị phân và danh sách node, tìm tổ tiên chung thấp nhất (LCA) của tất cả node trong danh sách. LCA là node thấp nhất mà tất cả node cho trước là con cháu của nó. Node coi là con cháu của chính nó.
Thuật toán
- Định nghĩa hàm fn(node):
- Nếu node là null: trả về node
- Nếu node nằm trong tập nodes: trả về node
- left := fn(node.left), right := fn(node.right)
- Nếu left và right đều không null: trả về node
- Ngược lại: trả về left hoặc right (cái nào không null)
- Chuyển danh sách node giá trị thành tập node tham chiếu (search_node)
- Gọi fn(root)
Code Python
import collections
class TreeNode:
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
def insert(temp, data):
que = [temp]
while que:
temp = que.pop(0)
if not temp.left:
temp.left = TreeNode(data) if data is not None else TreeNode(0)
break
else:
que.append(temp.left)
if not temp.right:
temp.right = TreeNode(data) if data is not None else TreeNode(0)
break
else:
que.append(temp.right)
def make_tree(elements):
Tree = TreeNode(elements[0])
for element in elements[1:]:
insert(Tree, element)
return Tree
def search_node(root, element):
if not root: return None
if root.data == element: return root
res1 = search_node(root.left, element)
if res1: return res1
return search_node(root.right, element)
def solve(root, node_list):
nodes = set(search_node(root, elem) for elem in node_list)
def fn(node):
if not node: return node
if node in nodes: return node
left, right = fn(node.left), fn(node.right)
return node if left and right else left or right
return fn(root)
root = make_tree([5, 3, 7, 2, 4, 6, 8])
print(solve(root, [6, 8]).data)
Input
make_tree([5, 3, 7, 2, 4, 6, 8]), [6, 8]
Output
7