原文只贴了一份 in-place 的中序展开代码。这里把题意、利用 BST 性质的关键观察以及递归返回值的语义补上，代码保持原样。
题目背景
题目要求：把一棵 BST（二叉搜索树） 原地（不能新建节点，只能改 left/right 指针）展开为一个有序的双向循环链表。BST 中节点 left 在新链表中作为前驱，right 作为后继；最后还要把链表头尾相连，形成循环。
概念解释
- BST 中序遍历有序：BST 的中序遍历序列必然是按值递增的，因此「按中序拼接」恰好等于「按从小到大顺序拼接」。
- 双向循环链表：每个节点既有前驱又有后继，且最后一个节点的
right指向第一个，第一个节点的left指向最后一个。 - 指针复用：本题不允许新建节点，所以中序遍历完成后必须用 BST 节点自身的
left/right字段充当链表的前驱/后继。
实现原理
inorder(root) 的语义是：把以 root 为根的子树就地拼成一段双向链表，并返回这段链表的最左节点（也就是子树最小值）。
- 递归处理 左子树，得到左侧已经成段的链表
h1；若左子树为空，则h1 = root。 - 沿
h1->right一直走到这段链表的末端，使其与root互为前驱后继，把root衔接到左段的尾部。 - 递归处理 右子树，得到右段的最左节点
h2，把root与h2互连；右段已是有序的，自然续在root之后。 - 整段子树展开后，最左节点仍然是步骤 1 得到的
h，将其作为返回值传给上一层。
最外层 treeToDoublyList 在拿到完整的 h 后，再走到末端节点 h1，把 h1->right 和 h->left 互连形成循环。
时间复杂度 O(n)，每个节点只在递归进入和”找尾巴”时被访问常数次；空间复杂度 O(h)（递归栈深度，h 为树高）。
参考实现
/*
// Definition for a Node.
class Node {
public:
int val;
Node* left;
Node* right;
Node() {}
Node(int _val) {
val = _val;
left = NULL;
right = NULL;
}
Node(int _val, Node* _left, Node* _right) {
val = _val;
left = _left;
right = _right;
}
};
*/
class Solution {
private:
// 函数式编程的思路，中序遍历，依次展开，然后，将链表的左侧与右侧连接在一起，
// 函数返回值为最左侧的节点
Node* inorder(Node* root)
{
Node* h1 = nullptr;
Node* h2 = nullptr;
Node* h = nullptr;
if(root == nullptr)
{
return nullptr;
}
if(root->left == nullptr){
// return root;
h1 = root;
// return h1;
}else
{
h1 = inorder(root->left);
}
h = h1;
while(h1->right != nullptr && h1 != root && h1->right != root)
{
h1 = h1->right;
}
if(root != h1)
{
root->left = h1;
h1->right = root;
}
if(root->right == nullptr)
{
h2 = nullptr;
}else{
h2 = inorder(root->right);
}
if(root != nullptr)
{
root->right = h2;
if(h2!=nullptr)
{
h2->left = root;
}
}
return h;
}
public:
Node* treeToDoublyList(Node* root) {
if(root == nullptr)
{
return nullptr;
}
Node* h = inorder(root);
// 循环双链表， 此处应该有优化空间
Node* h1 = h;
while(h1->right != nullptr)
{
// std::cout << h1->val << " " ;
h1 = h1->right;
}
h1->right = h;
h->left = h1;
return h;
}
};
