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

二叉搜索树与双向链表

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

最简单的思想,时间复杂度0(n),空间复杂度0(1),先用一个针,把树中的节点串一遍,即中序遍历把输出过程,改成单链表连接。然后遍历一遍链表,修改第二方向的指针,即可得到双链表。

# 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 ):
        # write code here
        if pRootOfTree == None:
            return pRootOfTree
        self.parent = None
        self.head = None
        self.dfs(pRootOfTree)
        if self.head.right == None:
            return self.head
        else:
            p1 = self.head
            p2 = self.head.right
            while p2!=None:
                p2.left = p1
                p1 = p2
                p2 = p2.right
        return self.head
    
    def dfs(self, pRoot):
        if pRoot == None:
            return
        self.dfs(pRoot.left)
        if self.parent == None:
            self.parent = pRoot
            self.head = pRoot
        else:
            self.parent.right = pRoot
            self.parent = pRoot
        self.dfs(pRoot.right)
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-07 11:35
程序员小白条:话太多,没实力和学历,差不多回答回答就行了,身份地位不一样
点赞 评论 收藏
分享
小浪_Coding:找硬件测试,也可兼顾软测欧, 简历还可以的 ,注意排版,项目写的有条理一点, 然后个人技能多加点, 润色好简历之后就开始沟通海投了,深圳,东莞这边做硬件相关的公司还不少, 医疗类,仪器类的都可以尝试
点赞 评论 收藏
分享
06-18 13:28
已编辑
门头沟学院 Web前端
爱睡觉的冰箱哥:《给予你300的工资》,阴的没边了
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
昨天 11:29
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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