企业官网建设流程全解析

他会给一个二叉搜索树，要求把他改为排好序的双向循环列表，并放回最小的值

对于二叉搜索树可以知道 对他进行中序遍历可以有序的获取到树中的元素，所以可以使用中序遍历来解决排序的问题

而如何将他改为双向链表按

既然时改为双向链表，那么前一个节点必须要知道，所以使用一个prev指针来维护和当前节点的前后指向关系，而我又要放回头节点，所以还需要一个head来记录头节点

对于这棵树 前序遍历一直到 1 节点，会触发修改节点指向的逻辑

这时head 为空 prev 为空，该节点也为最小的节点 所以head == 1节点， 而prev呢

他代表的时1 前面的节点，应该让1 节点的前驱 left 指向prev 然后prev 走到 1 节点，而prev为啥不维护后驱 prev.right呢 为空的嘛

继续回溯

当root 为2 节点

有prev不为空，这时就需要维护后驱了，prev.right = 2节点， 维护前驱 root.right= prev，

prev = root

这样就维护俩个节点之间的双向连接

最后退出递归时

head指向的时头 prev指向的时尾

需要再维护这俩个节点的连接然他们成为循环 前驱head.left=prev , 后驱prev.right=head

class Solution { Node pre, head; public Node treeToDoublyList(Node root) { if(root == null) return null; dfs(root); head.left = pre; pre.right = head; return head; } void dfs(Node root){ if(root == null) return; dfs(root.left); if(pre == null){ head = root; }else{ //后继 pre.right = root; } //前驱 root.left = pre; pre = root; dfs(root.right); } }