Giả sử chúng ta có một cây nhị phân. Chúng ta phải tìm tổ tiên chung gần nhất của hai nút cho trước. LCA của hai nút p và q là nút thấp nhất trong cây có cả p và q là hậu duệ. Ví dụ, nếu cây nhị phân là [3,5,1,6,2,0,8,null,null,7,4]. Cây sẽ như sau:
Ở đây LCA của 5 và 1 là 3.
Để giải quyết, chúng ta làm theo các bước sau:
Nếu cây rỗng, trả về null.
Nếu p và q đều giống root, trả về root.
left := LCA của cây con trái của root dùng p và q.
right := LCA của cây con phải của root dùng p và q.
Nếu left và right đều khác null, trả về root.
Trả về left hoặc right.
Ví dụ
class TreeNode:
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
def chen(temp, data):
hang_doi = []
hang_doi.append(temp)
while len(hang_doi):
temp = hang_doi[0]
hang_doi.pop(0)
if not temp.left:
if data is not None:
temp.left = TreeNode(data)
else:
temp.left = TreeNode(0)
break
else:
hang_doi.append(temp.left)
if not temp.right:
if data is not None:
temp.right = TreeNode(data)
else:
temp.right = TreeNode(0)
break
else:
hang_doi.append(temp.right)
def tao_cay(cac_phan_tu):
Cay = TreeNode(cac_phan_tu[0])
for phan_tu in cac_phan_tu[1:]:
chen(Cay, phan_tu)
return Cay
class Solution(object):
def lowestCommonAncestor(self, root, p, q):
if not root:
return None
if root.data == p or root.data == q:
return root
trai = self.lowestCommonAncestor(root.left, p, q)
phai = self.lowestCommonAncestor(root.right, p, q)
if trai and phai:
return root
return trai or phai
ob1 = Solution()
cay = tao_cay([3,5,1,6,2,0,8,None,None,7,4])
print(ob1.lowestCommonAncestor(cay, 5, 1).data)
Đầu vào
[3,5,1,6,2,0,8,null,null,7,4] 5 1
Đầu ra
3