Giả sử chúng ta có một cây tìm kiếm nhị phân, chúng ta phải chuyển đổi nó thành một danh sách được liên kết đơn lẻ bằng cách sử dụng trình tự chuyển ngang.
Vì vậy, nếu đầu vào giống như
thì đầu ra sẽ là [5, 4, 10, 2, 7, 15,]
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
head:=một nút danh sách được liên kết mới
-
currNode:=head
-
q:=một danh sách có giá trị gốc
-
trong khi q không trống, thực hiện
-
curr:=xóa phần tử đầu tiên khỏi q
-
nếu curr không phải là null, thì
-
next of currNode:=một nút danh sách liên kết mới có giá trị là curr
-
currNode:=next of currNode
-
chèn bên trái của lề đường vào cuối q
-
chèn lề đường bên phải vào cuối q
-
-
-
quay lại phần tiếp theo của đầu
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
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) Đầu vào
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)
Đầu ra
[5, 4, 10, 2, 7, 15, ]