剑指 Offer 36. 二叉搜索树与双向链表（中等）

题目：

class Solution {
public:
    Node* head=nullptr;
    Node* pre=nullptr;
    void traversal(Node* cur){   //二叉搜索树中序遍历的顺序就是构建双向链表的顺序
        if(!cur) return;
        traversal(cur->left);
        if(pre){      //若前置节点存在，则与当前节点建立双向链表关系
            pre->right=cur;
            cur->left=pre;
        }
        else{      //若不存在前置节点，说明该节点为头结点
            head = cur;
        }
        pre = cur;      //将当前节点设置为前置节点
        traversal(cur->right);
    }
    Node* treeToDoublyList(Node* root) {
        if(!root) return root;
        traversal(root);
        head->left = pre;      //最后要将头尾节点建立循环链表关系。pre递归到最后指向最后一个节点。
        pre->right = head;
        return head;      //返回的是头结点
    }
};

作者：林小鹿
链接：https://leetcode.cn/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/solutions/896127/tu-wen-bing-mao-zui-tong-su-yi-dong-de-t-0adg/
来源：力扣（LeetCode）