链表问题15——将搜索二叉树转换成双向链表

题目

将一颗搜索二叉树按照中序遍历(左-中-右)的顺序，变成一个有序的双向链表。

所谓的先序遍历、中序遍历和后序遍历都针对的是中间的节点也就是根节点，先序遍历为中-左-右，后序遍历为左-右-中

思路

方法一：用队列作容器，时空复杂度均为O(N)

1. 生成一个队列queue，按中序顺序遍历二叉树，并放入queue中
2. 依次从queue中弹出节点，并按弹出顺序重连即可。

源码

public class Node{public int value;public Node left;public Node right;public Node(int data){this.value=data;} 
}public Node convert1(Node head){Queue<Node> queue=new LinkedList<Node>();inOrderToQueue(head,queue);//poll功能和remove一样，不过当队列为空时，不报异常返回nullhead=queue.poll();Node pre=head;Node cur=null;Node left=null;while(!queue.isEmpty()){cur=queue.poll();pre.right=cur;cur.left=pre;pre=cur;}pre.right=null;return head;
}public void inOrderToQueue(Node head,Queue<Node> queue){if(head==null){return;}inOrderToQueue(head.left,queue);//offer 功能和add一样，不过当队列满后 不报异常会返回falsequeue.offer(head);inOrderToQueue(head.right,queue);
}