将二叉查找树转换成双链表

yingl · yingl · commit a768ae1cc0d7 · 2016-08-15T21:42:47.000+08:00
diff --git a/convert_binary_search_tree_to_doubly_linked_list.py b/convert_binary_search_tree_to_doubly_linked_list.py
@@ -0,0 +1,24 @@
+# -*- coding: utf-8 -*-
+
+class Solution:
+    def __init__(self):
+        self.head, self.tail = None, None
+
+    """
+    @param root, the root of tree
+    @return: a doubly list node
+    """
+    def bstToDoublyList(self, root):
+        # Write your code here
+        # 还是中序遍历，然后插入双链表节点。
+        if root:
+            self.bstToDoublyList(root.left)
+            node = DoublyListNode(root.val)
+            if not self.head:
+                self.head = node
+            else:
+                self.tail.next = node
+                node.prev = self.tail
+            self.tail = node
+            self.bstToDoublyList(root.right)
+        return self.head
