题解 | #二叉搜索树与双向链表#
二叉搜索树与双向链表
http://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5
先用中序遍历 然后是遍历是把 节点加入到列表中 而不是加入节点的值 。然后生成双链表。
def Convert(self , pRootOfTree ):
if pRootOfTree is None:return None
def proorder(root):
res,stack =[],[]
while stack or root:
while root:
stack.append(root)
root=root.left
node=stack.pop()
res.append(node)
root=node.right
return res
res=proorder(pRootOfTree)
if len(res)==1:
return res[0]
for i in range(len(res)-1):
res[i].right=res[i+1]
res[i+1].left=res[i]
return res[0]
