问题描述：输入一颗二叉排序树（BST），将其转换为一个排序的双向链表。
要求：不能创建任何新的节点，只能在调整树中的节点的指针方向。
思路：
1.二叉搜索树的特性是：中序遍历是有序的，单调递增的，左子树的元素的值都比根节点的元素值小，右子树的元素的值都比根节点的元素值大。
2.由BST的特性可以知道，BST转化为双向链表后，根节点的前一个元素是左子树的最右边节点，根节点的后一个元素是右子树的最左边节点。
3.左右子树的转换过程一致，所以是一个递归的过程。
4.最后，找出双向链表的头指针。（在左子树的最左边）
代码如下：
/**
* @author Aaron
* @date 2018/10/16 下午2:25
* @function BST转换为一个双向链表
*/
public class BSTConvertToDeList {
public static class TreeNode{
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val){
this.val = val;
}
}
public static TreeNode convert(TreeNode root){
if(root==null){
return null;
}
if(root.left!=null){
//先转换左子树，获得转换后的头指针
TreeNode leftHead = convert(root.left);
// 获得指向左子树的最后一个元素的指针
while (leftHead.right!=null){
leftHead = leftHead.right;
}
// 与root链接，注意双向
root.left = leftHead;
leftHead.right = root;
}
if (root.right!=null){
//先转换右子树，获得转换后的头指针
TreeNode rightHead = convert(root.right);
//获得指向右子树的最后一个元素的指针
while (rightHead.left!=null){
rightHead = rightHead.left;
}
//与root连接，注意双向
rightHead.left = root;
root.right = rightHead;
}
//找出双向链表的头指针（左子树的最左边）
while (root.left!=null){
root = root.left;
}
//返回双向链表的头指针
return root;
}
}
