สมมติว่าเรามีต้นไม้ไบนารีสองทรี เราต้องตรวจสอบลำดับของใบไม้จากซ้ายไปขวาในต้นไม้ทั้งสองต้นว่าเหมือนกันหรือไม่
ดังนั้นหากอินพุตเป็นแบบ
จากนั้นผลลัพธ์จะเป็น True เนื่องจากลำดับคือ [2, 6] สำหรับต้นไม้ทั้งสอง
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:
- c :=รายการใหม่
- กำหนดฟังก์ชัน inorder() สิ่งนี้จะหยั่งรากและค
- ถ้า c เป็นโมฆะ แล้ว
- c :=รายการใหม่
- ถ้ารูทไม่เป็นโมฆะ
- inorder(ด้านซ้ายของ root, c)
- ถ้าทางซ้ายของรูทเป็นโมฆะ และทางขวาของรูทเป็นโมฆะ ดังนั้น
- ใส่ค่าของ root ที่ส่วนท้ายของ c
- inorder(ทางขวาของรูท, c)
- คืนค
- จากวิธีหลัก ให้ทำดังนี้:
- ถ้า inorder(root0) เหมือนกับ inorder(root1) แล้ว
- คืนค่า True
- มิฉะนั้น
- คืนค่าเท็จ
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น:
ตัวอย่าง
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): if self.inorder(root0) == self.inorder(root1): return True else: return False 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) 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)
ผลลัพธ์
True
