题目

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

思路-递归

将根节点左孩子和右孩子都转换为双向链表，然后改变跟节点的left和right指针

实现

public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree==null){
            return null;
        }
        if(pRootOfTree.left==null&&pRootOfTree.right==null){
            return pRootOfTree;
        }
        TreeNode p=Convert(pRootOfTree.left);
        TreeNode q=Convert(pRootOfTree.right);
        //注:最后递归返回的是一个双向链表的头,所以左边生成的双向链表必须遍历一下找到结尾,右边的可以直接使用
        if(p!=null){
            while(p.right!=null){
                p=p.right;
            }
            p.right=pRootOfTree;
            pRootOfTree.left=p;
        }
        if(q!=null){
            pRootOfTree.right=q;
            q.left=pRootOfTree;
        }
        //遍历找到此次递归生成的双向链表的头
        while(pRootOfTree.left!=null){
            pRootOfTree=pRootOfTree.left;
        }
        return pRootOfTree;
    }