题解 |【清晰图解】 #二叉搜索树与双向链表#也不难

默认你已经理解题意

解题思路如下

先得搞明白什么是二叉搜索树？

是一棵有序的二叉树，所以我有时候也叫它二叉排序树。具备以下性质的二叉树我们称之为二叉搜索树：

1 若它的左子树不是空，那么左子树上的所有值均小于它的根节点；
2 若它的右子树不是空，那么右子树上所有值均大于它的根节点；

其中它的左子树和右子树其实也叫二叉搜索树。

二叉搜索树的中序遍历是：左=>根=>右；

所以二叉搜索树的中序遍历从小到大是有序的，对不对？

中序遍历模板

//打印中序遍历
void dfs(TreeNode* root ) 
{
        if(!root) return;
        dfs(root->left);    //左
        print(root->val);   //根
       dfs(root->right);    //右
}

下图，本题让我们要把一棵二叉搜索树变成排序的循环双向链表，像下面这样变

二叉搜索树的中序遍历本来就是有序的，这个我前面已经说过了😄，所以这道题就是在中序递归遍历的基础上改了一点点。

具体怎么做？

1、我们先定义两个指针 pre 和 head，pre指针用来保存中序遍历的前一个节点，head指针用于保存排序链表的头节点。

2、然后中序遍历二叉树，因为是中序遍历，所以遍历顺序就是这个双向链表的建立顺序了。所以我们只需要在中序遍历的过程中，修改每个节点的左右指针，然后把零散的节点连接成双向循环链表即可。

3、首先遍历二叉树的左子树，然后是当前根节点root

当前驱节点 pre 不是空时，把前驱节点pre的右指针指向当前根节点root，即pre->right = root。

当前驱节点 pre 为空的时候：代表head指针正在访问链表头节点，记为 head = root ，保存头节点。

4、每一个root节点访问的时候它的左子树肯定被访问过了，所以你放心大胆修改它的left指针，把root的left指针指向它的前驱节点，即 root->left = pre，这样两个节点之间的双向指针就改好了。

5、然后前驱节点pre右移到当前root节点，接下来递归到右子树重复上述四步操作。

6、完成以上各步后，只是把二叉树变成了双向排序链表，我们还需要将链表的首尾连接到一起，将其变成双向循环排序链表。

下面这样操作

head->left = pre;

pre->right = head;

时间复杂度分析下

n是二叉树的节点数，中序遍历需要访问所有节点，所以时间复杂度是O(n)

//c++这样写
class Solution {
public:
    Node* pre = nullptr, *head = nullptr;
    Node* treeToDoublyList(Node* root) {
        if (!root) return root;
        dfs(root);
        head->left = pre;
        pre->right = head;
        return head;
    }
    void dfs(Node* root){
        if (!root) return;// 递归边界: 叶子结点返回
        dfs(root->left);  //左子树
        if (pre) pre->right = root;
        else head = root; // 保存链表头结点
        root->left = pre; 
        pre = root;
        dfs(root->right); //右子树
    }
};

//Java这样写
class Solution {
    Node pre = null, head = null;
    public Node treeToDoublyList(Node root) {
        if (root == null) return root;
        dfs(root);
        head.left = pre;
        pre.right = head;
        return head;
    }
     void dfs(Node root){
        if (root == null) return; // 递归边界: 叶子结点返回
        dfs(root.left);
        if (pre != null) pre.right = root;
        else head = root; // 链表头结点
        root.left = pre;
        pre = root;
        dfs(root.right);
    }
}