สมมติว่าเรามีต้นไม้ไบนารี เราต้องหาโหนดบรรพบุรุษร่วมที่ต่ำที่สุดของสองโหนดที่กำหนด LCA ของสองโหนด p และ q เป็นโหนดที่ต่ำที่สุดในทรีที่มีทั้ง p และ q เป็นโหนด ดังนั้นถ้าไบนารีทรีเป็นเหมือน [3,5,1,6,2,0,8,null,null,7,4] ต้นไม้จะเป็นเช่น −
LCA ของ 5 และ 1 คือ 3
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- ถ้าต้นไม้ว่างเปล่า ให้คืนค่า null
- ถ้า p และ q ทั้งคู่เหมือนกับรูท ให้ส่งคืนรูท
- left :=LCA ของทรีย่อยด้านซ้ายของรูทโดยใช้ p และ q
- right :=LCA ของทรีย่อยด้านขวาของรูทโดยใช้ p และ q
- ถ้าทั้งซ้ายและขวาไม่เป็นศูนย์ ให้คืนค่ารูท
- กลับซ้ายหรือขวา
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
class TreeNode: def __init__(self, data, left = None, right = None): self.data = data self.left = left self.right = right def insert(temp,data): que = [] que.append(temp) while (len(que)): temp = que[0] que.pop(0) if (not temp.left): if data is not None: temp.left = TreeNode(data) else: temp.left = TreeNode(0) break else: que.append(temp.left) if (not temp.right): if data is not None: temp.right = TreeNode(data) else: temp.right = 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 class Solution(object): def lowestCommonAncestor(self, root, p, q): if not root: return None if root.data == p or root.data ==q: return root left = self.lowestCommonAncestor(root.left, p, q) right = self.lowestCommonAncestor(root.right, p, q) if right and left: return root return right or left ob1 = Solution() tree = make_tree([3,5,1,6,2,0,8,None,None,7,4]) print(ob1.lowestCommonAncestor(tree, 5, 1).data)
อินพุต
[3,5,1,6,2,0,8,null,null,7,4] 5 1
ผลลัพธ์
3
