剑指offer 牛客网 二叉搜索树和双向链表
# -*- coding: utf-8 -*-
"""
Created on Tue Apr 9 18:58:36 2019 @author: Administrator
题目：
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。
要求不能创建任何新的结点，只能调整树中结点指针的指向。
思路：
step1:采用递归中序遍历的方式，将值放在列表中
step2:遍历将其转换成双向链表
""" class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def Convert(self, pRootOfTree):
# write code here
if pRootOfTree: #判断边界条件，判空
res = [] #用于存放中序的节点
res = self.InOrder(res,pRootOfTree) #中序遍历
for index in range(len(res)-1):
if res[index]: #当节点不空进入
res[index].right = res[index+1] #前向串联
res[index+1].left = res[index] #反向串联
return res[0] #返回头结点
else: #若为空直接返回
return None
#递归的中序遍历
def InOrder(self,res,pRootOfTree):
if pRootOfTree:
self.InOrder(res,pRootOfTree.left) #遍历左子节点
res.append(pRootOfTree) #将根节点加入到列表中
self.InOrder(res,pRootOfTree.right) #遍历右子节点
return res
#打印双向的链表
def Print2list(self,head):
while head:
print(head.val)
head = head.right #从前往后遍历
#head = head.left #从后往前遍历
if __name__ == '__main__':
solution = Solution()
#1 2 3 4 5 6 7
node_left = TreeNode(1)
node_right = TreeNode(3)
root_left = TreeNode(2)
root_left.left = node_left
root_left.right = node_right node_left = TreeNode(5)
node_right = TreeNode(7)
root_right = TreeNode(6)
root = TreeNode(4)
root.left = root_left
root_right.left = node_left
root_right.right = node_right
root.right = root_right head = solution.Convert(root)
solution.Print2list(head)