本题比较重要的有两点：
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); } };