排序列表转换为二分查找树

yingl · yingl · commit a9ad8cda91c9 · 2016-07-30T11:03:58.000+08:00
diff --git a/convert_sorted_list_to_balanced_bst.py b/convert_sorted_list_to_balanced_bst.py
@@ -0,0 +1,33 @@
+# -*- coding: utf-8 -*-
+
+class Solution:
+    """
+    @param head: The first node of linked list.
+    @return: a tree node
+    """
+    def sortedListToBST(self, head):
+        # write your code here
+        if not head:
+            return None
+        # &#36890;&#36807;&#20004;&#20010;&#25351;&#38024;&#65292;&#19968;&#20010;&#19968;&#27493;&#19968;&#20010;&#20004;&#27493;&#23558;&#38142;&#34920;&#20998;&#20026;&#21069;&#21518;&#20004;&#27573;&#12290;
+        first_node, second_node = head, head.next
+        prev = None
+        while second_node:
+            if second_node:
+                second_node = second_node.next
+                if second_node:
+                    second_node = second_node.next
+                    prev = first_node
+                    first_node = first_node.next
+                else:
+                    break
+            else:
+                break
+        new_head = first_node.next
+        if prev:
+            prev.next = None
+        root = TreeNode(first_node.val)
+        if head != first_node:
+            root.left = self.sortedListToBST(head)
+        root.right = self.sortedListToBST(new_head)
+        return root
