题解 | #二叉搜索树与双向链表#

二叉搜索树与双向链表

http://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5

解题步骤:
1)用递归得到二叉搜索树的中序遍历结果并存入列表 order里。注意:这里列表中存的是每个节点而非value
2)遍历列表order并生成双向链表。在这里要注意index=0和len(order)-1时的操作。

边界用例:
二叉树为None或只有一个节点时


# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

#
# 
# @param pRootOfTree TreeNode类 
# @return TreeNode类
#
class Solution:
    def Convert(self , pRootOfTree ):
        
        def inorder(root,order):
            if root ==None:
                return None
            inorder(root.left, order)
            order.append(root)   #[list] order里加入的是一个节点而非value
            inorder(root.right,order)
            
        
        if not pRootOfTree:
            return None

        list_order=[]
        inorder(pRootOfTree, list_order)
        if len(list_order)==1:
            return pRootOfTree
        for i in range(len(list_order)):
            if i==0:
                list_order[i].left=None
            else:
                list_order[i].left=list_order[i-1]
            if i==len(list_order)-1:
                list_order[i].right=None
            else:
                list_order[i].right=list_order[i+1]
        return list_order[0]
        # write code here


全部评论

相关推荐

半解316:内容充实,细节需要修改一下。 1,整体压缩为一页。所有内容顶格。 2,项目描述删除,直接写个人工作量 修改完之后还需要建议,可以私聊
点赞 评论 收藏
分享
完美的潜伏者许愿简历...:隐藏信息被你提取出来了,暗示,这就是暗示
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务