home

หน้าแรก
 Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> Python

โปรแกรมเพื่อสำรวจไบนารีทรีโดยใช้รายการทิศทางใน Python

สมมติว่าเรามีไบนารีทรีและรายการสตริงที่ประกอบด้วย "R" (ขวา) "L" (ซ้าย) และ "U" (ขึ้น) เริ่มต้นจากรูท เราต้องสำรวจต้นไม้โดยทำการเคลื่อนไหวแต่ละครั้งโดยที่:"R" หมายถึงสำรวจไปยังลูกที่ถูกต้อง "L" หมายถึงการเลื่อนไปทางซ้ายของลูก "U" หมายถึงการข้ามไปยังระดับบนสุด

ดังนั้นหากอินพุตเป็นแบบ

โปรแกรมเพื่อสำรวจไบนารีทรีโดยใช้รายการทิศทางใน Python

["R","R","U","L"] แล้วเอาท์พุตจะเป็น 3

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

  • อดีต :=รายการใหม่

  • สำหรับการเคลื่อนไหวแต่ละครั้งให้ทำ

    • แทรกรูตที่ส่วนท้ายของอดีต

    • หากการเคลื่อนไหวเหมือนกับ "L" แล้ว

      • root :=เหลือรูท

    • มิฉะนั้นเมื่อการเคลื่อนไหวเหมือนกับ "R" แล้ว

      • root :=ด้านขวาของรูท

    • มิฉะนั้น

      • ลบองค์ประกอบสุดท้ายจากอดีต

      • root :=องค์ประกอบสุดท้ายจากอดีตและลบออกจากอดีต

  • ส่งคืนค่ารูท

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.val = data
      self.left = left
      self.right = right
class Solution:
   def solve(self, root, moves):
      past = []
      for move in moves:
         past.append(root)
         if move == "L":
            root = root.left
         elif move == "R":
            root = root.right
         else:
            past.pop()
            root = past.pop()
      return root.val
ob = Solution()
root = TreeNode(2)
root.right = TreeNode(4)
root.right.left = TreeNode(3)
root.right.right = TreeNode(5)
traverse = ["R","R","U","L"]
print(ob.solve(root, traverse))

อินพุต

root = TreeNode(2) root.right = TreeNode(4) root.right.left =
TreeNode(3) root.right.right = TreeNode(5) ["R","R","U","L"]

ผลลัพธ์

3