26.二叉搜索树与双向链表

题目描述

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

思路

根节点将left连接到左子树的最右节点，

将right连接到右子树的最左节点

需要注意的是，我们要返回的是头节点，即最左边的节点，所以递归返回的是最左边的节点

右子树的最左边节点和根节点之间可以互相连接，但是左子树需要找到最右，并且当leftNode为空时，返回的应该是根节点本身

下面看代码

 1 class Solution:
 2     def Convert(self, pRootOfTree):
 3         # write code here
 4         if pRootOfTree == None:
 5             return None
 6         def find_right(node):
 7             while node.right:
 8                 node=node.right
 9             return node
10         
11         leftNode = self.Convert(pRootOfTree.left)
12         rightNode = self.Convert(pRootOfTree.right)
13         
14         retNode = leftNode
15         if leftNode:
16             leftNode = find_right(leftNode)
17         else:
18             retNode = pRootOfTree
19             
20         pRootOfTree.left = leftNode
21         pRootOfTree.right = rightNode
22         
23         if leftNode !=None :
24             leftNode.right = pRootOfTree
25         if rightNode !=None:
26             rightNode.left = pRootOfTree
27         return retNode

2019-12-17 16:40:17