目录

一、题目内容

二、解题思路

三、代码

一、题目内容

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

给定的有序链表： [-10, -3, 0, 5, 9],

一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：

      0
     / \
   -3   9
   /   /
 -10  5

二、解题思路

快慢指针，快指针走两步，慢指针走一步，快指针走完，慢指针到中间，然后使慢指针下一个为空，用慢指针构造节点，左子树传入head，右子树传入慢指针的next，递归反复。

三、代码

  

   

    

     

    
    

     

      # Definition for singly-linked list.
     
    
   

    

     

    
    

     

      class ListNode:
     
    
   

    

     

    
    

     
 def __init__(self, val=0, next=None):
     
    
   

    

     

    
    

     

       self.val = val
     
    
   

    

     

    
    

     

       self.next = next
     
    
   

    

     

    
    

     

      # Definition for a binary tree node.
     
    
   

    

     

    
    

     

      class TreeNode:
     
    
   

    

     

    
    

     
 def __init__(self, val=0, left=None, right=None):
     
    
   

    

     

    
    

     

       self.val = val
     
    
   

    

     

    
    

     

       self.left = left
     
    
   

    

     

    
    

     

       self.right = right
     
    
   

    

     

    
    

     

      class Solution:
     
    
   

    

     

    
    

     
 def sortedListToBST(self, head: ListNode) -> TreeNode:
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 def dfs(head):
     
    
   

    

     

    
    

     
 if head is None:
     
    
   

    

     

    
    

     
 return None
     
    
   

    

     

    
    

     
 if head and head.next is None:
     
    
   

    

     

    
    

     
 return TreeNode(head.val)
     
    
   

    

     

    
    

     

       slow, fast, pre = head, head, None
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 while fast and fast.next:
     
    
   

    

     

    
    

     

       pre = slow
     
    
   

    

     

    
    

     

       slow = slow.next
     
    
   

    

     

    
    

     

       fast = fast.next.next
     
    
   

    

     

    
    

     

       pre.next = None
     
    
   

    

     

    
    

     

       node = TreeNode(slow.val)
     
    
   

    

     

    
    

     

       node.left = dfs(head)
     
    
   

    

     

    
    

     

       node.right = dfs(slow.next)
     
    
   

    

     

    
    

     
 return node
     
    
   

    

     

    
    

     
 return dfs(head)
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      if __name__ == '__main__':
     
    
   

    

     

    
    

     

       nums = [-10, -3, 0, 5, 9]
     
    
   

    

     

    
    

     

       a = ListNode(nums[0])
     
    
   

    

     

    
    

     

       cur = a
     
    
   

    

     

    
    

     

       i = 1
     
    
   

    

     

    
    

     
 while cur:
     
    
   

    

     

    
    

     
 if i == len(nums):
     
    
   

    

     

    
    

     
 break
     
    
   

    

     

    
    

     

       cur.next = ListNode(nums[i])
     
    
   

    

     

    
    

     

       cur = cur.next
     
    
   

    

     

    
    

     

       i += 1
     
    
   

    

     

    
    

     

       s = Solution()
     
    
   

    

     

    
    

     

       ans = s.sortedListToBST(a)
     
    
   

    

     

    
    

     

       print(ans)
     
    
  
 

文章来源: nickhuang1996.blog.csdn.net，作者：悲恋花丶无心之人，版权归原作者所有，如需转载，请联系作者。

原文链接：nickhuang1996.blog.csdn.net/article/details/108707769