温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

剑指offer:二叉搜索树与双向链表

发布时间:2020-07-07 07:48:17 来源:网络 阅读:429 作者:Jayce_SYSU 栏目:编程语言

题目描述
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。

# -*- coding: utf-8 -*-
# @Time         : 2019-07-07 11:03
# @Author       : Jayce Wong
# @ProjectName  : job
# @FileName     : BST2LinkedList.py
# @Blog         : https://blog.51cto.com/jayce1111
# @Github       : https://github.com/SysuJayce

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

class Solution:
    """
    由于二叉搜索树BST的中序遍历就是从小到大的,符合有序链表的定义,那么可以考虑从中序遍历着手。

    如果按照中序遍历,假设当前转换到了根节点,那么左子树已经转换完成,即左子树中的最大节点应该是当
    前链表中的末尾节点,因此根节点的左指针应该指向该末尾节点,同时该末尾节点的右指针应该指向根节点。
    当把左子树和根节点转换完成之后,用同样的办法转换右子树。

    也就是利用递归方法,先转换左子树然后根节点最后右子树。**关键在于要保存当前链表中的末尾节点**
    """
    def Convert(self, pRootOfTree):
        if not pRootOfTree:
            return None
        pLastNodeInList = self.convertNode(pRootOfTree, None)
        # 需要返回链表的头节点
        pHeadOfList = pLastNodeInList
        while pHeadOfList and pHeadOfList.left:
            pHeadOfList = pHeadOfList.left

        return pHeadOfList

    def convertNode(self, pNode, pLastNodeInList):
        if not pNode:
            return None
        pCurrent = pNode
        # 先转换左子树
        if pCurrent.left:
            pLastNodeInList = self.convertNode(pCurrent.left, pLastNodeInList)

        # 然后将当前节点和当前链表的末尾节点链接起来
        pCurrent.left = pLastNodeInList
        # 这里需要判断当前节点是不是链表的头节点,如果是,那么pLastNodeInList是None
        if pLastNodeInList:
            pLastNodeInList.right = pCurrent

        # 在链接过后,当前节点就是链表的末尾节点
        pLastNodeInList = pCurrent
        # 然后对右子树进行转换
        if pCurrent.right:
            pLastNodeInList = self.convertNode(pCurrent.right, pLastNodeInList)

        return pLastNodeInList
向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI