面试题36：二叉搜索树与双向链表
题目：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
二叉搜索树转为排序的链表，还只能调整指针，可借鉴中序遍历的形式：
def inorder(self, node):
if node == None:
return
probe = node
self.inorder(probe.left)
print(probe.data)
self.inorder(probe.right)
核心需由打印/存储节点的值改为更改指针：
- probe指向的节点的左节点是上一个节点，
- 上一个节点的右节点是probe指向的节点。
为了实现这一核心，需构造变量last_node = None，递归版和非递归版的解法如下：
class ConvertBinarySearchTree:
def __init__(self):
self.last_node = None
def Convert(self, root):
# write code here
if root is None:
return None
def recurse(node):
probe = node
if probe.left:
recurse(probe.left)
probe.left = self.last_node
if self.last_node:
self.last_node.right = probe
self.last_node = probe
if probe.right:
recurse(probe.right)
recurse(root)
# 遍历到双链表的头节点
while root.left:
root = root.left
return root
def convert_non_recurse(self, root):
# 非递归解法
if root is None:
return None
stack = []
node = root
last_node = None
while stack or node:
while node:
stack.append(node)
node = node.left
node = stack.pop()
node.left = last_node
if last_node:
last_node.right = node
last_node = node
node = node.right
while root.left:
root = root.left
return root
另有配套测试，其中TreeTest见这篇文章：
def link_list(head):
"""return list of link"""
lyst = []
while head:
lyst.append(head.data)
head = head.right
return lyst
if __name__ == "__main__":
from TreeTest import *
whole = test_whole_group()
left = test_left_group()
right = test_right_group()
one = test_one()
solution = ConvertBinarySearchTree()
whole_result = solution.convert_non_recurse(whole)
left_result = solution.convert_non_recurse(left)
right_result = solution.convert_non_recurse(right)
one_result = solution.convert_non_recurse(one)
assert link_list(whole_result) == [4, 6, 8, 10, 12, 14, 16]
assert link_list(left_result) == [1, 2, 3, 4, 5]
assert link_list(right_result) == [1, 2, 3, 4, 5]
assert link_list(one_result) == [1]
assert solution.convert_non_recurse(None) is None
