Convert Binary Search Tree to Sorted Doubly Linked List （Tree)

Convert a BST to a sorted circular doubly-linked list in-place. Think of the left and right pointers as synonymous to the previous and next pointers in a doubly-linked list.

A circular doubly-linked list. Think of the left and right pointers in a tree as synonymous to the previous and next pointers in a list.

The idea is using in-order traversal set previous visited node's left node points to current node, and current node's right node points to previous visited node.

How do we set head's left points to last and the last's right points to head? We just need to keep the head node and let it's left points to the current node, and current node's right points to the head node.

edge case: root node only, we need to point left and right to root itself.

分析

就是树的Inorder 加上prev cur之类的指针

from TreeNode import TreeNode


class Solution:
    def bstToSortedDLL(self,root):
        head = TreeNode(-1)
        head.right = root

        stack = []
        cur,prev = root,None
        first = True
        while cur or stack:
            while cur:
                stack.append(cur)
                cur = cur.left
            cur = stack.pop()
            if first:
                head.right = cur
                first = False
            if prev:
                prev.right = cur
                cur.left = prev

            prev = cur
            cur = cur.right

        if prev:
            prev.right = head.right
            head.right.left = prev
        return head

    def print_list(self,head):

        """Function to print the given
           doubly linked list"""
        if head is None:
            return

        while head:
            print(head.val)
            head = head.right


root = TreeNode(10)
root.left = TreeNode(12)
root.right = TreeNode(15)
root.left.left = TreeNode(25)
root.left.right = TreeNode(30)
root.right.left = TreeNode(36)
obj = Solution()
head = obj.bstToSortedDLL(root)
obj.print_list(head)

recursive：这里最后的prev就是最后的node,和head串起来就行了

    head = prev =  None
    def bstToSortedDLLRe(self, root):
        if not root:
            return
        self.bstToSortedDLLRe(root.left)
        if not self.prev:
            self.head = root
        else:
            self.prev.right = root
            root.left = self.prev
        self.prev = root
        self.bstToSortedDLLRe(root.right)


    def helper(self,root):
        self.bstToSortedDLLRe(root)
        self.prev.right = self.head
        self.head.left = self.prev