将二叉搜索树原地转换成排序的双向链表

布满荆棘的人生 2023-07-14 05:23 22阅读 0赞

双向链表的每一个节点有next和pre两个指针，二叉树的每个节点则有right和left两个指针，其中next，right指针都指向的是比当前节点大的下一个节点，pre和left指针则指向的是比当前节点小的前一个节点，所以我们把二叉搜索树中的right指针当做双向链表的next指针，left则与pre对应，这样通过中序遍历改变指针的指向，就可得到一个从小到大有序的双向链表。  
这里可以有两种写法，一种就是正常的左中右的中序遍历方式，维护头尾两个指针。改变尾指针的指向将链表串起来。

class BST2DL:
        def __init__(self):
            self.head = None
            self.tail = None
            
        def convert(self, root):
            if not root:
                return
            self.convert(root.left)
            if not self.head:
                self.head, self.tail = root, root
            else:
                #前一个尾节点的右孩子指向当前根节点，即双向链表中的后向指针next
                #当前根节点的左孩子指向前一个尾节点，即前向指针prev
                self.tail.right, root.left = root, self.tail
                self.tail = self.tail.right   #更新尾节点
            self.convert(root.right)
            return self.head

第二种写法，维护一个头指针即可，但是遍历方式需要变成右中左这样的“中序遍历”，也就是从最右遍历到最左，这样的话，当遍历到最小节点时，头指针也刚好指向这个最小节点。这里改变的就是头指针的指向，其实两种方式差不多。

class Solution:        
        def convert(self, root):
            head = None
            def helper(root):
                nonlocal head
                if not root:
                    return
                helper(root.right)   #右
                if not head:
                    head = root     #根
                else:
                    root.right = head
                    head.left = root
                    head = root
                #print(head.val)
                helper(root.left)    #左
            helper(root)
            return head

#验证第二种写法
    #从头到尾打印节点
    s = Solution()
    head = s.convert(bst.root)
    while head.right:
        print(head.val, end=' -> ')
        head = head.right
    print(head.val)
    
    #从尾到头打印节点
    while head:
        print(head.val, end=' -> ')
        head = head.left

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7  
7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 ->