将搜索二叉树转换成双向链表

问题重述：

给与一颗搜索二叉树，将其转换为一个有序的双向链表，并将链表的头返回
例如：

这棵搜索二叉树转换后的双向链表从头到尾依次是1～9。对每一个节点来说，原来的right指针等价于转换后的next 指针，原来的left 指针等价于转换后的last 指针，最后返回转换后的双向链表头节点

问题分析：

方法一：二叉树转化后的双向链表顺序和二叉树的中序遍历顺序一样，我们可以先中序遍历二叉树，将得到的每一个结点保存起来（先进的先出，所以使用队列最合适），然后遍历队列将每一个结点弹出来并且相互连接

解题：

代码：

方法一：二叉树的遍历

public static Node convertTree1(Node head) {
		Queue<Node> queue = new LinkedList<Node>();
		inorderToQueue(head,queue);
		if(queue.isEmpty()) {
			return head;
		}
		head = queue.poll();
		Node pre = head;
		Node next = null;
		Node cur = null;
		while(!queue.isEmpty()) {
			cur = queue.poll();
			pre.right = cur;
			cur.left = pre;
			pre = cur;
		}
		pre.right = null;
		return head;
		
	}
	public static void inorderToQueue(Node head,Queue<Node> queue) {
		if(head == null) {
			return;
		}
		inorderToQueue(head.left,queue);
		queue.offer(head);
		inorderToQueue(head.right,queue);
		
	}

代码解析：使用递归的方式来对二叉树进行遍历

总结：

二叉树的遍历：

二叉树有四种遍历方式，分别是前序遍历、中序遍历、后序遍历和层次遍历

前序遍历：顺序为根节点、左节点、右节点

中序遍历：顺序为左节点、根节点、右节点

后序遍历：顺序为左节点、右节点、根节点

层次遍历：从上往下一层一层遍历，同一层按照从左往右的顺序

遍历二叉树最简单的实现方法是使用递归的方式：

// 递归实现
public static void inorderToQueue(Node head) {
		if(head == null) {
			return;
		}
    	// 按照顺序来，现在使用的是中序遍历，顺序为左、根、右，如果想要使用其他遍历方式，就改变顺序即可
		inorderToQueue(head.left);
		// 对当前结点你要做的操作
		inorderToQueue(head.right);
		
	}

遍历二叉树也可以不使用递归方式，但是会比较麻烦，需要特别注意结点是否为空，一般前中后三种遍历方式都需要使用栈来操作，层次遍历使用队列进行辅助操作