class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
a = ListNode(-10)
b = ListNode(-3)
c = ListNode(0)
d = ListNode(5)
e = ListNode(9)
# a = ListNode(-10)
a.next = b
b.next = c
c.next = d
d.next = e
# 這道題大方向考慮的是遞回，遞回的進行找到每一個節點，
# 每一個節點就是當前鏈表的中間節點，如果是偶數，那就是中間靠右節點，
# 注意每次找到中間節點后要把鏈表分開，左邊是左子樹，右邊是右子樹
class Solution:
def sortedListToBST(self, head: ListNode) -> TreeNode:
return self.dfs(head,None)
# 定義函式尋找中間節點
def search_node(self,head,tail):
# 用快慢指標的方法來尋找，
slow,fast = head,head
while fast != tail and fast.next != tail:
slow = slow.next
fast = fast.next.next
# 最后慢指標的位置，就是我們需要的
return slow
def dfs(self,head,tail):
# 頭指標指向鏈表頭節點，尾指標指向鏈表尾節點，
# 如果頭節點和尾節點重合，說明不需要進行遍歷了，
if head == tail :return
# 尋找中間節點
node = self.search_node(head,tail)
print(node.val)
# 然后將中間節點變成二叉樹的節點
root = TreeNode(node.val)
# 尋找左子樹
root.left = self.dfs(head,node)
# 尋找右子樹
root.right = self.dfs(node.next,tail)
return root
A = Solution()
A.sortedListToBST(a)
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/47306.html
標籤：Python