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

二叉搜索树与双向链表

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

用list存储中序遍历结果在顺序连接起来,但是这样做空间复杂度是O(N),看了解题思路,需要在中序遍历过程中改变指针指向,之后来尝试下。

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
        self.res = []
        # 中序bianli
        self.midtra(pRootOfTree)
        if len(self.res)==0:
            return None
        root = self.res[0]
        pre = None 
        if len(self.res) == 1:
            return self.res[0]
        for i in range(len(self.res)-1):
            self.res[i].left = pre 
            self.res[i].right = self.res[i+1]
            pre=self.res[i]
        self.res[-1].left = self.res[i]
        return root

    def midtra(self,root):
        # 中序遍历
        if root==None:
            return 
        self.midtra(root.left)
        self.res.append(root)
        self.midtra(root.right)

root = TreeNode(1)
root.right = TreeNode(2)
root.right.right = TreeNode(3)
root.right.right.right = TreeNode(4)
root = Solution().Convert(root)
cur=root
while cur:
    print(cur.val)
    cur = cur.right

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-08 13:05
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-04 15:36
点赞 评论 收藏
分享
屌丝逆袭咸鱼计划:心态摆好,man,晚点找早点找到最后都是为了提升自己好进正职,努力提升自己才是最关键的😤难道说现在找不到找的太晚了就炸了可以鸡鸡了吗😤早实习晚实习不都是为了以后多积累,大四学长有的秋招进的也不妨碍有的春招进,人生就这样
点赞 评论 收藏
分享
评论
点赞
1
分享

创作者周榜

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