資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝學
法學Python程式：將連結串列轉換為二叉搜尋樹
假設我們有一個大小為 n 的已排序連結串列節點，我們需要建立一個二叉搜尋樹。方法是：取 k = floor(n / 2) ，將第 k 個節點的值設定為根節點。然後，遞迴地使用連結串列中第 k 個節點左側的節點構建左子樹，並遞迴地使用連結串列中第 k 個節點右側的節點構建右子樹。
因此，如果輸入為 [2,4,5,7,10,15]，則輸出為…
為了解決這個問題，我們將遵循以下步驟：
定義一個名為 solve() 的方法，它將接收一個節點作為引數。
如果節點為空，則
返回 null
如果節點的下一個節點為空，則
返回一個值為該節點值的新樹節點。
slow := node, fast := node
prev := None
當 fast 和 fast 的下一個節點都不為空時，執行以下操作：
prev := slow
slow := slow 的下一個節點
fast := fast 的下一個節點的下一個節點
prev 的下一個節點 := None
root := 一個值為 slow 的新樹節點
root 的左子節點 := solve(node)
root 的右子節點 := solve(slow 的下一個節點)
返回 root
讓我們來看下面的實現，以便更好地理解：
示例
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.data = data self.left = left self.right = right def make_list(elements): head = ListNode(elements[0]) for element in elements[1:]: ptr = head while ptr.next: ptr = ptr.next ptr.next = ListNode(element) return head def print_tree(root): if root is not None: print_tree(root.left) print(root.data, end = ', ') print_tree(root.right) class Solution: def solve(self, node): if not node: return None if not node.next: return TreeNode(node.val) slow = fast = node prev = None while fast and fast.next: prev = slow slow = slow.next fast = fast.next.next prev.next = None root = TreeNode(slow.val) root.left = self.solve(node) root.right = self.solve(slow.next) return root ob = Solution() head = make_list([2,4,5,7,10,15]) root = ob.solve(head) print_tree(root)
輸入
[2,4,5,7,10,15]
輸出
2, 4, 5, 7, 10, 15,
更新於：2020年10月10日
960 次瀏覽
廣告