输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。
Solutions
解法一:可以将二叉树分成三个部分,那么链表的顺序其实就是二叉树的中序遍历结果,我们可以设立两个方法,一个遍历出结果,二一个将结点的前后指针对应连接起来,当前结点的 next 指针指向下一个结点的 left,当前结点的 pre 指针指向前一个结点的 right。
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def __init__(self):
self.attr = []
def inOrder(self, pNode):
# write code here
if not pNode:
return
self.inOrder(pNode.left)
self.attr.append(pNode)
self.inOrder(pNode.right)
def Convert(self, pRootOfTree):
# write code here
if not pRootOfTree:
return None
self.inOrder(pRootOfTree)
for i, node in enumerate(self.attr[:-1]):
node.right = self.attr[i+1]
self.attr[i+1].left = node
return self.attr[0]
解法二:递归式,将特定节点的左指针指向其左子树中的最后子节点,将其右指针指向其右子树中的最左子节点,依次递归,调整好全部节点的指针指向。
# -*- coding:utf-8 -*-
# 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 not pRootOfTree:
return
root=pHead=pRootOfTree
while pHead.left:
pHead=pHead.left
self.Core(root)
return pHead
def Core(self,root):
if not root.left and not root.right:
return
if root.left:
preRoot=root.left
self.Core(root.left)
while preRoot.right:
preRoot=preRoot.right
preRoot.right=root
root.left=preRoot
if root.right:
nextRoot=root.right
self.Core(root.right)
while nextRoot.left:
nextRoot=nextRoot.left
nextRoot.left=root
root.right=nextRoot