【剑指Offer刷题小记】二叉搜索树与双向链表（JAVA版）

快一年没写代码了，重新刷一遍剑指Offer，简单记录一下

题目描述：输入一颗二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的节点。

思路分析：二叉搜索树特点是每个节点的左孩子都比该节点小，右孩子都比该节点大，因此中序遍历的序列恰好是按照从小到大的顺序排列。并且对于每个节点的左右子树，在中序遍历后，左子树的最右节点与该子树的父节点相邻，右子树的最左节点与该子树的父节点相邻。可以用递归的思路，将每棵子树进行中序遍历得到双向链表，父节点与左子树的最右节点相连，与右子树的最左节点相连即可。

代码如下：

head指向当前链表的最右节点，realHead指向链表头节点便于最后的返回。