二叉搜索树与双向链表

牛客网：二叉搜索树与双向链表

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。
要求不能创建任何新的结点，只能调整树中结点指针的指向。
二叉树搜索树：根结点的左边都比根结点小，根结点的右边都比根结点大

解题思路：
第一步：中序遍历 左 根 右
第二步：把左当作前驱，把右当后驱

TreeNode2 prev=null;//标记上一个结点
    public void ConvertChild(TreeNode2 pCur){
        if(pCur==null){
            return;
        }
        ConvertChild(pCur.left);//6
        pCur.left=prev;//置为null

        if(prev !=null){
            prev.right=pCur;//5
        }

        prev=pCur;
        ConvertChild(pCur.right);
    }
    //返回的是双向链表的头结点
    public TreeNode2 Convert(TreeNode2 pRootOfTree) {
        ConvertChild(pRootOfTree);
        TreeNode2 head=pRootOfTree;

        while (head!=null && head.left !=null){
            head=head.left;
        }
        return head;
    }