题解 | #二叉搜索树与双向链表#

题目描述

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

注意:
1.要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继
2.返回链表中的第一个节点的指针
3.函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构
4.你不用输出或者处理，示例中输出里面的英文，比如"From left to right are:"这样的，程序会根据你的返回值自动打印输出

题目分析

题目要求生成的双向链表，是二叉搜索的中序遍历结果（从小到大的顺序），对遍历的结果修改左右结点指向。
具体的指针变化，如图
树结构指针，叶子结点的左右指针指向都为空；

生成的双向链表结点指针；

解题思路

1.使用二叉树的中序遍历可以获得一个要求链表结点的访问顺序；
2.在这个顺序中，我们要存储当前的结点cur和访问前的结点pre（cur的值一定是比pre小的），
3.修改pre和cur的左右指向，cur.right = pre; pre.left = cur;
中序遍历核心代码

Node pre;
Node cur;
dfs(root){
   // 递归左节点
   dfs(root.left);
   // 处理结点指针
   cur.right = pre;
   pre.left = cur;
   cur = pre;
   // 递归右节点
   dfs(root.right);
}

代码实现

使用全局成员变量cur表示遍历的当前结点，head表示树的最左结点（也就是生成的链表的头结点），在递归遍历过程中，参数pRootOfTree就表示当前结点的前一个结点，修改结点的左右指针指向。

    private TreeNode cur = null;
    private TreeNode head = null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null) return null;
        Convert(pRootOfTree.left);
        // 关键点结点指针的指向
        if(cur == null){
            // 最左结点作为根节点
            cur = pRootOfTree;
            head = pRootOfTree;
        }else{
            // 不是最左结点的转化
            cur.right = pRootOfTree;
            pRootOfTree.left = cur;
            cur = pRootOfTree;
        }
        Convert(pRootOfTree.right);
        return head;
    }

递归遍历整个树，时间复杂度：O(n)；
当树退化为链表时，递归深度达到n，空间复杂度：O(n)。