【链表问题】打卡10：将搜索二叉树转换成双向链表
前言
以专题的形式更新刷题贴，欢迎跟我一起学习刷题，相信我，你的坚持，绝对会有意想不到的收获。每道题会提供简单的解答，如果你有更优雅的做法，欢迎提供指点，谢谢。
注：如果代码排版出现了问题麻烦通知我下，谢谢。
【题目描述】
对于二叉树的节点来说，有本身的值域，有指向左孩子和右孩子的两个指针；对双向链表的节点来说，有本身的值域，有指向上一个节点和下一个节点的指针。在结构上，两种结构有相似性，现有一棵搜索二叉树，请将其转为成一个有序的双向链表。 节点定义：
1class Node2{
2 public int value;
3 public Node2 left;
4 public Node2 right;
5
6 public Node2(int value) {
7 this.value = value;
8 }
9}例如：
这棵二查搜索树转换后的双向链表从头到尾依次是 1～9。对于每一个节点来说，原来的 right 指针等价于转换后的 next 指针，原来的 left 指针等价于转换后的 last 指针，最后返回转换后的双向链表的头节点。
【要求】
如果链表的长度为 N, 时间复杂度达到 O(N)。
【难度】
尉：★★☆☆
【解答】
方法一：采用队列辅助
如果用一个队列来辅助的话，还是挺容易。采用中序遍历的方法，把二叉树的节点全部放进队列，之后在逐一弹出来连接成双向链表。
代码如下
1public static Node2 convert1(Node2 head) {
2 Queue<Node2> queue = new LinkedList<>();
3 //将节点按中序遍历放进队列里
4 inOrderToQueue(head, queue);
5 head = queue.poll();
6 Node2 pre = head;
7 pre.left = null;
8 Node2 cur = null;
9 while (!queue.isEmpty()) {
10 cur = queue.poll();
11 pre.right = cur;
12 cur.left = pre;
13 pre = cur;
14 }
15 pre.right = null;
16 return head;
17}
18
19private static void inOrderToQueue(Node2 head, Queue<Node2> queue) {
20 if (head == null) {
21 return;
22 }
23 inOrderToQueue(head.left, queue);
24 queue.offer(head);
25 inOrderToQueue(head.right, queue);
26}这种方法的时间复杂度为 O(n), 空间复杂度也为 O(n)。
方法2：通过递归的方式
在之前打卡的9道题中，几乎超过一半都用到了递归，如果这些题目使用的递归大家都理解了，并且能够自己独立写出代码了，那么我相信大家对递归的思想、使用已经有一定的熟练性。
我们假设函数conver的功能就是把二叉树变成双向链表，例如对于这种一棵二叉树：
经过conver转换后变成这样：
注意，转换之后，把最右边节点的right指针指向了最左边的节点的。
对于下面这样一颗二叉树：
采用conver函数分别对左右子树做处理，结果如下：
之后，再把他们连接起来
了解了基本原理之后，直接看代码吧。
1public static Node2 conver(Node2 head) {
2 if (head == null) {
3 return head;
4 }
5 Node2 leftE = conver(head.left);
6 Node2 rightE = conver(head.right);
7 Node2 leftB = leftE != null ? leftE.right : null;
8 Node2 rightB = rightE != null ? rightE.right : null;
9 if (leftE != null && rightE != null) {
10 leftE.right = head;
11 head.left = leftE;
12 head.right = rightB;
13 rightB.left = head;
14 rightE.right = leftB;
15 return rightE;
16 } else if (leftE != null) {
17 leftE.right = head;
18 head.left = leftE;
19 head.right = leftB;
20 return head;
21 } else if (rightE != null) {
22 head.right = rightB;
23 rightB.left = head;
24 rightE.right = head;
25 return rightE;
26 } else {
27 head.right = head;
28 return head;
29 }
30}时间复杂度为O(n),空间复杂度为O(h)，其中h是二叉树的高度。
原理虽然不难，但写起代码，还是有挺多细节需要注意的，所以一直强调，有时间的话，一定要自己手打一遍代码，有时你以为自己懂了，可能在写代码的时候，发现自己并没有懂，一写就出现很多bug。