Cho cây nhị phân có con trỏ parent và hai node x, y. Tìm LCA của x, y. LCA là node thấp nhất mà x, y đều là con cháu.
Thuật toán
- Tạo đường đi từ x lên root: path_p_r = []
- Duyệt x lên parent, thêm vào path_p_r
- Duyệt y lên parent, nếu y có trong path_p_r → trả về y (đó là LCA)
Code Python
class TreeNode:
def __init__(self, data, left=None, right=None, parent=None):
self.data = data
self.left = left
self.right = right
self.parent = parent
def insert(temp, data):
que = [temp]
while que:
temp = que.pop(0)
if not temp.left:
temp.left = TreeNode(data, parent=temp) if data is not None else TreeNode(0, parent=temp)
break
else:
que.append(temp.left)
if not temp.right:
temp.right = TreeNode(data, parent=temp) if data is not None else TreeNode(0, parent=temp)
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(x, y):
path_p_r = []
while x:
path_p_r.append(x)
x = x.parent
while y:
if y in path_p_r:
return y
y = y.parent
root = make_tree([5, 3, 7, 2, 4, 1, 7, 6, 8, 10])
print(solve(search_node(root, 3), search_node(root, 7)).data)
Input
[5, 3, 7, 2, 4, 1, 7, 6, 8, 10], 3, 7
Output
5