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

二叉搜索树与双向链表

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

全部评论

相关推荐

不愿透露姓名的神秘牛友
今天 11:55
点赞 评论 收藏
分享
门口唉提是地铁杀:之前b站被一个游戏demo深深的吸引了。看up主页发现是个初创公司,而且还在招人,也是一天60。二面的时候要我做一个登录验证和传输文件两个微服务,做完要我推到github仓库,还要我加上jaeger和一堆运维工具做性能测试并且面试的时候投屏演示。我傻乎乎的做完以后人家跟我说一句现在暂时不招人,1分钱没拿到全是白干
你的秋招第一场笔试是哪家
点赞 评论 收藏
分享
每晚夜里独自颤抖:要求太多的没必要理
点赞 评论 收藏
分享
码农索隆:这种hr,建议全中国推广
点赞 评论 收藏
分享
评论
点赞
1
分享

创作者周榜

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