引出问题 

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示：

数据范围：输入二叉树的节点数[0,1000]，二叉树中每个节点的值0≤val≤1000 要求：空间复杂度O(1) (即在原树上操作），时间复杂度 O(n)

注意: 1.要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继 2.返回链表中的第一个节点的指针 3.函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构 4.你不用输出双向链表，程序会根据你的返回值自动打印输出

 分析解答

通过题目，我们可以把问题分解成两个主要部分： 1.怎么有序 2.二叉搜索树怎么解决前驱和后继的问题

1.怎么有序

我们都知道，对于二叉搜索树，中序遍历可以使它的节点进行有序排列，所以要转换成有序的双向链表，自然而然在操作的时候就应该用中序来进行遍历。

public void convertChild(TreeNode cur) {
        if (cur == null) {
            return;
        }
        convertChild(cur.left);
        
        //操作

        convertChild(cur.right);

    }

2.二叉搜索树怎么解决前驱和后继的问题

当我们对搜索树进行压缩拉长后，我们会发现这个结构，正是我们要求的双向链表结构。

解决前驱后继，我们便需要一个prev来表示前一位节点，一个cur来表示当前节点，prev保留着上一位操作的节点，用cur来进行遍历，在每一次操作中，用cur.left=prev语句来完成操作节点前驱的操作，用prev.right=cur来完成操作节点前一个节点后继的操作。操作完成后再利用prev=cur来完成顺序的遍历。

注意点：第一个节点的前驱是null，所以我们在设置prev的时候默认为null，这样就可以确保在第一次操作cur.left=prev的时候有正确的指向。同时，在进行语句prev.right=cur的时候应该加以条件(prev!=null)避免出现空指针异常。在最后一个节点的时候，不需要对其后继进行操作，因为在二叉搜索树的每一个节点的left和right都是默认为null。

public TreeNode prev = null;

public void convertChild(TreeNode cur) {
        if (cur == null) {
            return;
        }
        convertChild(cur.left);

        cur.left = prev;

        if (prev != null) {
            prev.right = cur;
        }

        prev = cur;

        convertChild(cur.right);

    }

整体代码 

public TreeNode prev = null;

    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null){
            return null;

        }
        convertChild(pRootOfTree);
        TreeNode head = pRootOfTree;
        while(head.left != null){   //pRootOfTree表示二叉树头结点，应该返回链表头结点！！！
            head = head.left;
        }
        return head;
    }
    public void convertChild(TreeNode cur) {
        if (cur == null) {
            return;
        }
        convertChild(cur.left);

        cur.left = prev;

        if (prev != null) {
            prev.right = cur;
        }

        prev = cur;

        convertChild(cur.right);

    }