資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚學
法律研究將樹的層次遍歷轉換為 Python 中的連結串列的程式
假設我們有一個二叉搜尋樹，我們必須使用層次遍歷將其轉換為單鏈表。
所以，如果輸入類似於
那麼輸出將為 [5, 4, 10, 2, 7, 15, ]
為了解決這個問題，我們將按照以下步驟進行 −
head := 一個新的連結串列節點
currNode := head
q := 一個帶有根值列表
當 q 不為空時，執行
curr := 刪除 q 中的第一個元素
如果 curr 不為空，則
currNode 的 next := 一個帶有 curr 值的新連結串列節點
currNode := currNode 的 next
插入 q 末尾的 curr 左側
插入 q 末尾的 curr 右側
返回 head 的 next
讓我們看看以下實現以更好地理解 −
示例
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, ]
更新於： 2020 年 10 月 10 日
337 次瀏覽
廣告