二叉排序树（BST）转双向链表

问题描述：输入一颗二叉排序树（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;
    }
}