หา LCA ของ 2 โหนดใน binary tree โดยไม่มี parent pointer ใช้ DFS post-order: ถ้าโหนดปัจจุบันเป็นเป้าหมาย (x หรือ y) และซ้ายหรือขวาคืนค่าไม่ใช่ None -> โหนดนี้คือ LCA ถ้าทั้งซ้ายและขวาคืนค่าไม่ใช่ None -> โหนดนี้คือ LCA มิฉะนั้นคืนค่าที่ไม่ใช่ None
อัลกอริทึม
- DFS function dfs(node) คืนค่าโหนดที่เจอเป้าหมายหรือ LCA
- ถ้า node เป็น x หรือ y: ตรวจสอบ left/right ถ้ามีเจออีกตัวคืน node (LCA)
- Recursive left, right
- ถ้า left และ right ทั้งคู่ไม่ใช่ None: node คือ LCA
- คืน left หรือ right (ตัวที่ไม่ใช่ None)
ตัวอย่างโค้ด
class TreeNode:
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
def make_tree(elements):
Tree = TreeNode(elements[0])
for element in elements[1:]:
insert(Tree, element)
return Tree
def solve(root, x, y):
def dfs(node):
if not node: return None
if node in [x, y]:
left = dfs(node.left)
right = dfs(node.right)
if left or right:
return node
left = dfs(node.left)
right = dfs(node.right)
if left and right:
return node
return left or right
return dfs(root)
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) # Output: 3
อินพุต/เอาต์พุต
Input: tree, nodes 2 and 4 Output: 3
