二叉搜索树的中序遍历

题目链接-来源：力扣（LeetCode）

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。

思路：

要将BST的节点从小到大以循环双向链表串起来。注意BST的节点从小到大访问生成的序列即是中序遍历，所以我们可以以中序遍历为模板解决此题。
我们需要用两个变量分别记录 中序遍历的当前节点 和 前驱节点。对于递归做法，用全局变量会比较方便，对于非递归做法，则用普通变量即可。我采用的是非递归做法，事实上，递归做法的代码会更加简洁明了。
在遍历的同时调整 当前节点 和 前驱节点 的指针。注意，由于是循环链表，遍历完成后还要记得链接头节点和末尾节点。

时间复杂度：O(n)
空间复杂度：O(n)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    public Node treeToDoublyList(Node root) {
        Stack<Node> s = new Stack<>();
        ArrayList<Node> list = new ArrayList<>();
        Node cur = root;
        while (!s.isEmpty() || cur != null) {
            if (cur != null) {
                s.push(cur);
                cur = cur.left;
            } else {
                Node visit = s.pop();
                list.add(visit);
                cur = visit.right;
            }
        }
        int n = list.size();
        Node head = null;
        
        if (n > 0) {
            head = list.get(0);
            Node last = list.get(n - 1);
            head.left = last;
            last.right = head;
        }
        for (int i = 1; i < n; i++) {
            Node node = list.get(i);
            Node pre = list.get(i - 1);
            node.left = pre;
            pre.right = node;
        }
        
        return head;
    }
}