https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/
这道题用AVL-tree做的确有一点夸张，而且更慢，但是权当是复习一下AVL-Tree的构建了。

个人解答

  1. # Definition for singly-linked list.
  2. # class ListNode:
  3. #     def __init__(self, val=0, next=None):
  4. #         self.val = val
  5. #         self.next = next
  6. # Definition for a binary tree node.
  7. # class TreeNode:
  8. #     def __init__(self, val=0, left=None, right=None):
  9. #         self.val = val
  10. #         self.left = left
  11. #         self.right = right
  12. class Solution:
  13.     def sortedListToBST(self, head: ListNode) -> TreeNode:
  14.         self.height = collections.defaultdict(int)
  16.         def getHeight(node):
  17.             if not node:
  18.                 return -1
  19.             return self.height[node]
  21.         def updateHeight(node):
  22.             self.height[node] = max(getHeight(node.left), getHeight(node.right)) + 1
  24.         def leftRotation(root):
  25.             newRoot = root.right
  26.             root.right = newRoot.left
  27.             newRoot.left = root
  28.             updateHeight(newRoot)
  29.             updateHeight(root)
  30.             return newRoot
  32.         def insert(root, val):
  33.             if not root:
  34.                 return TreeNode(val)
  36.             root.right = insert(root.right, val)
  37.             if getHeight(root.right) - getHeight(root.left) > 1:
  38.                 root = leftRotation(root)
  40.             updateHeight(root)
  42.             return root
  44.         res = None
  46.         while head:
  47.             res = insert(res, head.val)
  48.             head = head.next
  49.         return res

题目分析

AVL的构建，很标准的一个流程。
注意updateHeight，别忘了，rotation之后也要更新两个height。

其它解法

这道题，分治，加上一点链表操作的trick，应该写的更加简单，而且效率也更高。

  1. class Solution:
  2.     def sortedListToBST(self, head: ListNode) -> TreeNode:
  3.         def f(l, r):
  4.             if l == r:
  5.                 return None
  6.             slow, fast = l, l
  7.             while fast != r and fast.next != r:
  8.                 slow = slow.next
  9.                 fast = fast.next.next
  10.             root = TreeNode(slow.val)
  11.             root.left = f(l, slow)
  12.             root.right = f(slow.next, r)
  13.             return root
  14.         return f(head, None)

这个解法也可以写成迭代的，不过没有递归来的清晰。