LeetCode题解——36.二叉搜索树与双向链表（中序遍历）

 目录

一.解题思路

二.代码实现

---

题目地址：剑指 Offer 36. 二叉搜索树与双向链表 - 力扣（LeetCode）

一.解题思路

这是一道很好的锻炼递归思维和提升对于二叉树熟练度的题目。

 本题的解题思路是中序遍历+递归。

因为题目要求左指针指前驱，右指针指后继，所以此时节点在中间位置。这符合中序遍历的思路，因此使用中序遍历来操作。

在此基础上，左边递归之后会产生一个node作为本节点的前驱prev，将node与本节点互指即可。

在右递归之前，我们将本节点作为prev，因为本节点一定是右边某节点的前驱。

这样，大体思路就出来了。至于头节点和尾节点的连接，将prev置为空，第一次操作prev与某节点互指时，该节点就是头节点。当二叉树全部遍历结束时，prev所指就是尾。

这是基于中序遍历的基本特点：第一个值是树左下角节点，最后一个是树右下角节点。

这样讲可能还有些不清楚，换一个说法：

我们在操作一个节点时，只需要先递归左节点，找到本节点的前驱。完成前驱与本节点对接后，将本节点作为前驱，递归右子树，与右子树中本节点的后继对接即可。

二.代码实现

class Solution {
public:
    Node* prev = nullptr;//前驱
    Node* head = nullptr;//用来标记头节点
    void CreatListMidMerge(Node* now)
    {
        if(now == nullptr) return;//节点空，返回
        creat(now->left);//左递归
        if(prev) //与前驱对接
        {
            prev->right = now;
            now->left = prev;
        }
        else head = now;//else: prev为空，节点是头节点
        prev = now;//本节点置为prev
        creat(now->right);//右递归
    }
    Node* treeToDoublyList(Node* root) {
        if(root == nullptr) return root;//判空
        CreatListMidMerge(root);
        head->left = prev;//头尾互连
        prev->right = head;
        return head;
    }
};

当你认为你的代码是不会有错误时，这就更难了。——Steve McConnell 《代码大全》

---

如有错误，敬请斧正