# 美团面经 426.将二叉排序树转换为双向循环链表
**思路：迭代的中序遍历 + 维护遍历过程中的pre节点与curr节点**

```java []
public static Tree solution(Tree head){
        Tree p = head;
        Tree pre = null;//中序遍历的前驱节点
        Tree curr = null;//中序遍历的当前节点
        Tree res = null;//指向虚拟双向链表的头节点
        boolean isHead = false;
        Deque<Tree> stack = new LinkedList<>();
        while(!stack.isEmpty() || p != null){
            while(p != null){
                stack.push(p);
                p = p.left;
            }
            p = stack.pop();

            if(!isHead){
                res = p;
                isHead = true;
            }
            pre = curr;
            curr = p;
            if(pre != null){
                pre.right = curr;
            }
            curr.left = pre;

            p = p.right;
        }

        //将头尾连接起来形成一个双向循环链表
        res.left = curr;
        curr.right = res;
        return res;
    }
```

```java测试用例 []
public class test15 {
    static class Tree{
        int val;
        Tree left;
        Tree right;
        Tree(int val){
            this.val = val;
        }
    }

    public static void main(String[] args) {
        Tree head = new Tree(4);
        Tree node = new Tree(2);
        head.left = node;
        head.right = new Tree(5);
        node.left = new Tree(1);
        node.right = new Tree(3);
        Tree res = solution(head);
        Tree p = res;
        for(int i = 0; i < 10; i++){
            System.out.println(p.val);
            p = p.right;
        }

        for(int i = 0; i < 10; i++){
            System.out.println(p.val);
            p = p.left;
        }
    }
}
```




求职面试

美团面经 426.将二叉排序树转换为双向循环链表
思路：迭代的中序遍历 + 维护遍历过程中的pre节点与curr节点