สมมติว่าเรามีแผนผังการค้นหาแบบไบนารี เราต้องแปลงเป็นรายการที่เชื่อมโยงโดยลำพังโดยใช้การข้ามผ่านของลำดับชั้น
ดังนั้นหากอินพุตเป็นแบบ
จากนั้นผลลัพธ์จะเป็น [5, 4, 10, 2, 7, 15, ]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
head :=โหนดรายการที่เชื่อมโยงใหม่
-
currNode :=หัว
-
q :=รายการที่มีค่ารูท
-
ในขณะที่ q ไม่ว่างให้ทำ
-
curr :=ลบองค์ประกอบแรกออกจาก q
-
ถ้าค่าเคอร์เซอร์ไม่เป็นโมฆะ
-
ถัดไปของ currNode :=โหนดรายการที่เชื่อมโยงใหม่พร้อมค่าของสกุลเงิน
-
currNode :=ถัดไปของ currNode
-
แทรกด้านซ้ายของเคอร์เซอร์ที่ส่วนท้ายของ q
-
ใส่เคอร์เซอร์ขวาที่ท้าย q
-
-
-
กลับหัวถัดไป
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
class ListNode:
def __init__(self, data, next = None):
self.val = data
self.next = next
class TreeNode:
def __init__(self, data, left = None, right = None):
self.val = data
self.left = left
self.right = right
def print_list(head):
ptr = head
print('[', end = "")
while ptr:
print(ptr.val, end = ", ")
ptr = ptr.next
print(']')
class Solution:
def solve(self, root):
head = ListNode(None)
currNode = head
q = [root]
while q:
curr = q.pop(0)
if curr:
currNode.next = ListNode(curr.val)
currNode = currNode.next
q.append(curr.left)
q.append(curr.right)
return head.next
ob = Solution()
root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(10)
root.left.left = TreeNode(2)
root.right.left = TreeNode(7)
root.right.right = TreeNode(15)
head = ob.solve(root)
print_list(head) อินพุต
root = TreeNode(5) root.left = TreeNode(4) root.right = TreeNode(10) root.left.left = TreeNode(2) root.right.left = TreeNode(7) root.right.right = TreeNode(15) head = ob.solve(root)
ผลลัพธ์
[5, 4, 10, 2, 7, 15, ]
