将二叉搜索树转换为已排序的双向链接列表

https://www.lintcode.com/problem/1534/?utm_source=sc-cheatsheet-cyc

描述

将BST转换为已排序的循环双向链表。可以将左右指针视为双向链表中上一个和下一个指针的同义词。

我们以下面的BST为例，它可以帮助您更好地理解问题：

我们希望将此BST转换为循环双向链表。双向链表中的每个节点都有一个前任和后继。对于循环双向链表，第一个元素的前导是最后一个元素，最后一个元素的后继是第一个元素。

下图显示了上述BST的循环双向链表。“head”符号表示它指向的节点是链表的最小元素。

具体来说，我们希望进行转型。转换后，树节点的左指针应指向其前一个指针，右指针应指向其后继指针。我们应该将指针返回到链表的第一个元素。

下图显示了转换后的BST。实线表示后继关系，而虚线表示前趋关系。

样例

样例 1:

输入: {4,2,5,1,3}        4       /  \      2   5     / \    1   3输出: "left:1->5->4->3->2  right:1->2->3->4->5"解释:left：逆序输出right：正序输出

样例 2:

输入: {2,1,3}        2       /  \      1   3输出: "left:1->3->2  right:1->2->3"

解题思路：

1. 构建二叉树：根据输入的数组构建对应的二叉搜索树。

2. 左子树逆序输出：对二叉树的左子树进行后序遍历，并将结果逆序输出。

3. 右子树正序输出：对二叉树的右子树进行前序遍历，并将结果正序输出。

```python
"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""
# 分治法，得到左右链表，再和root连起来
class Solution:
    """
    @param root: root of a tree
    @return: head node of a doubly linked list
    """
    def treeToDoublyList(self, root):
        # Write your code here.
        if not root:
            return root
        head = self.traverse(root)
        tail = head
        while tail.right:
            tail = tail.right
        tail.right = head
        head.left = tail
        return head
        
    def traverse(self, root) -> TreeNode:
        if not root: #一般不需要判断到叶子
            return root
        head = root  
        #注意这里判断左右子树是否存在，不存在的话直接返回根节点。
        if root.left:  
            leftNode = self.traverse(root.left)
            head = leftNode
            while leftNode.right:
                leftNode = leftNode.right
            leftNode.right = root
            root.left = leftNode
        if root.right:
            rightNode = self.traverse(root.right)
            root.right = rightNode
            rightNode.left = root
             
        return head
        


    
```