> For the complete documentation index, see [llms.txt](https://nataliekung.gitbook.io/ladder_code/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://nataliekung.gitbook.io/ladder_code/qiang-hua-4-shuang-zhi-zhen-ff09/jiang-er-cha-sou-suo-shu-zhuan-huan-wei-yi-pai-xu-de-shuang-xiang-lian-jie-lie-biao.md).

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

描述

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

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

![bstdlloriginalbst](https://assets.leetcode.com/uploads/2018/10/12/bstdlloriginalbst.png)

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

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

![bstdllreturndll](https://assets.leetcode.com/uploads/2018/10/12/bstdllreturndll.png)

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

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

![bstdllreturnbst](https://assets.leetcode.com/uploads/2018/10/12/bstdllreturnbst.png)

样例

**样例 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
        


    
```
````