มีต้นไม้แบบทวิภาค 2 ต้น ตรวจสอบว่าลำดับใบ (left-to-right) เหมือนกันหรือไม่
เช่น ต้นไม้ทั้งคู่มีใบ [2,6] ให้ True
ขั้นตอนการแก้ปัญหา
- Inorder traversal เก็บค่าใบ (โหนดที่ไม่มีลูก) ใน list
- เปรียบเทียบ list ทั้งสอง
ตัวอย่างโค้ด
class TreeNode:
def __init__(self, data, left=None, right=None):
self.val = data; self.left = left; self.right = right
class Solution:
c = []
def inorder(self, root, c=None):
if c is None: c = []
if root:
self.inorder(root.left, c)
if not root.left and not root.right: c.append(root.val)
self.inorder(root.right, c)
return c
def solve(self, root0, root1):
return self.inorder(root0) == self.inorder(root1)
ob = Solution()
root1 = TreeNode(1); root1.right = TreeNode(3); root1.right.left = TreeNode(2); root1.right.right = TreeNode(6)
root2 = TreeNode(1); root2.left = TreeNode(3); root2.right = TreeNode(6); root2.left.left = TreeNode(2)
print(ob.solve(root1, root2))
อินพุต
root1 = TreeNode(1) ... root2 = TreeNode(1) ...
เอาต์พุต
True
