Python 两种方法实现

二叉搜索树与双向链表

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

方法一:使用额外空间,中序遍历按大小保存树节点,再处理左右指针的指向

class Solution:
    def Convert(self, pRootOfTree):
        if not pRootOfTree:
            return None
        self.tree = []
        self.dfs(pRootOfTree)
        if len(self.tree) == 1:
            return self.tree[0]
        for i in range(len(self.tree)):
            if i == 0:
                self.tree[i].right = self.tree[i+1]
            elif i == len(self.tree)-1:
                self.tree[i].left = self.tree[i-1]
            else:
                self.tree[i].left = self.tree[i-1]
                self.tree[i].right = self.tree[i+1]
        return self.tree[0]
    def dfs(self, root):
        if not root:
            return 
        self.dfs(root.left)
        self.tree.append(root)
        self.dfs(root.right)

方法二:不使用额外空间,在进行中序遍历时,对左右指针指向进行处理

class Solution:
    def Convert(self, pRootOfTree):
        if not pRootOfTree:
            return None
        root = self.dfs(pRootOfTree, None)
        while root.left:
            root = root.left
        return root

    def dfs(self, root, last_node): # 额外参数,当前已遍历节点的最大
        if not root:
            return None
        if root.left: # 处理左子树
            last_node = self.dfs(root.left, last_node) # 返回左子树的最大值节点
        root.left = last_node # 当前节点的左指针的指向左子树最大值节点
        if last_node: # 左子树的最大值节点的右指针指向当前节点
            last_node.right = root # 
        last_node = root # 更新已处理节点的最大值节点
        if last_node.right: # 处理右子树
            last_node = self.dfs(root.right, last_node)
        return last_node
全部评论

相关推荐

hso_:哈哈哈哈哈哈我没offer一样在同一道题开喷了
投递深圳同为数码等公司10个岗位
点赞 评论 收藏
分享
喜欢走神的孤勇者练习时长两年半:爱华,信华,等华,黑华
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务