Cho cây nhị phân và hai node x, y. Tìm LCA - node thấp nhất mà x, y đều là con cháu. Node coi là con cháu của chính nó.
Thuật toán
- DFS(node):
- Nếu node null: return
- Nếu node là x hoặc y: DFS(left), DFS(right); nếu left hoặc right có giá trị → ans=node, return node
- left = DFS(left), right = DFS(right)
- Nếu left và right đều không null: ans=node, return node
- Return left or right
- Gọi dfs(root), trả về ans
Code Python
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, x, y):
ans = None
def dfs(node):
nonlocal ans
if not node:
return
if node in [x, y]:
left = dfs(node.left)
right = dfs(node.right)
if left or right:
ans = node
return node
left = dfs(node.left)
right = dfs(node.right)
if left and right:
ans = node
return node
return left or right
dfs(root)
return ans
root = make_tree([5, 3, 7, 2, 4, 1, 7, 6, 8, 10])
print(solve(root, search_node(root, 2), search_node(root, 4)).data)
Input
make_tree([5, 3, 7, 2, 4, 1, 7, 6, 8, 10]), search_node(root, 2), search_node(root, 4)
Output
3