剑指 Offer 36. 二叉搜索树与双向链表

本题比较重要的有两点：

1.一般认为有序的二叉搜索树，都是中序遍历。

2.中序遍历的递归顺序，得到的就是排好序的，就是链表的顺序，因此只需管遍历的过程中的链表指向即可。

class Solution {
public:
    // pre将来指向尾节点，head指向头节点
    Node *pre = nullptr, *head = nullptr;
    Node* treeToDoublyList(Node* root) {
        if(root == nullptr) return root;
        dfs(root);
        head->left = pre;
        pre->right = head;
        return head;
    }
    void dfs(Node *root) {
        if(root == nullptr) return;
        dfs(root->left);  // 左子树
        // 前驱节点右指针指向当前节点
        if(pre != nullptr) pre->right = root;
        // 否则链表正在访问头节点
        else head = root; // 保存链表头节点
        root->left = pre;
        pre = root;
        dfs(root->right);
    }
};