题目分析

这个题目虽然标签为中等，实际上却是一个简单题。主要考察二叉树的中序遍历，小伙伴们先想一想如何求解？

递归

我们要将BST转化为双向循环列表，可以进行中序遍历，将遍历到的节点都存放起来，然后在数组中将这些节点相互连接。

算法的**时间复杂度为$O(n)$，空间复杂度为$O(n)$**。

class Solution(object):
    def treeToDoublyList(self, root):
        """
        :type root: Node
        :rtype: Node
        """
        def inorder(node):
            if not node:
                return
            inorder(node.left)
            array.append(node)
            inorder(node.right)

        array = []
        inorder(root)
        lens = len(array)
        for i in range(lens):
            array[i].right = array[(i + 1) % lens]
            array[i].left = array[(i - 1) % lens]
        return array[0] if lens else root

优化递归

我们将这些节点都保存在数组中，其实是一种投机取巧的方法，除了栈空间外还用到了额外的数组空间，而且每个节点也遍历了两次，递归时访问了一次，遍历数组时又访问了一次，虽然时间复杂度和空间复杂度都是$O(n)$，但是相对复杂了一些。

我们能否在递归的时候就完成链表操作呢？答案是可以的，只需要添加一个pre变量，指向上一个节点，当前节点执行时，pre.right = node, node.left = pre即可，最后pre = node，就可以实现递归时完成双向链表操作。

算法的**时间复杂度为$O(n)$，空间复杂度为$O(n)$**。

class Solution(object):
    def treeToDoublyList(self, root):
        """
        :type root: Node
        :rtype: Node
        """
        def inorder(node):
            if not node:
                return
            nonlocal pre, head
            inorder(node.left)
            if pre:
                node.left, pre.right = pre, node
            else:
                head = node
            pre = node
            inorder(node.right)

        if not root:
            return None
        pre, head = None, None
        inorder(root)
        head.left, pre.right = pre, head
        return head

刷题总结

许多小伙伴们说我为什么博客更新的慢或者刷题数量好少，几天才刷一道题目。其实不是这样的，博客里的题目都是我在笔试面试中遇到的题目，或者刷题时不会做的题目或者是有意义的题目才会给大家分享，有时也会遇到一些简单的题目，就没有必要去写，因此写在博客里的题目更值得小伙伴们去思考。