java中序遍历-二叉搜索树与双向链表

题目描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
解题思路
按照中序遍历的顺序就是排序的顺序。因此只需要在中序遍历中进行指针的改变
用一个公共指针记录已遍历完成的前一个节点
那么只需让当前节点的left指向公共节点，公共节点的right指向当前节点
然后当前节点为公共节点即可
之后就是递归

暴力思路就是用数组存储中序遍历的结果再按结果进行指针的修改，不再赘述
bu***记录：必须分成两个函数与实现。因为涉及到递归，所以会执行多次中序，而最终查找头结点需要在递归完成之后，不然会修改指针的指向

** java代码**

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    private TreeNode node=null;//记录当前遍历的节点
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree==null) return null;
        midorder(pRootOfTree);//在中序遍历中完成对指针的修改
        while(pRootOfTree.left!=null && pRootOfTree != null){
            //必须先修改完指针，才能按照最后的结果进行头结点的寻找
            //原本的根节点位于中间，直接向前寻找即可
            pRootOfTree=pRootOfTree.left;
        }
        return pRootOfTree;
    }
    public void midorder(TreeNode pRootOfTree){//在中序遍历中完成对指针的修改
        if(pRootOfTree==null) return ;
        midorder(pRootOfTree.left);
        pRootOfTree.left=node;
        if(node != null){
            node.right=pRootOfTree;
        }
        node=pRootOfTree;
        midorder(pRootOfTree.right);
    }
}