将一个 二叉搜索树 就地转化为一个 已排序的双向循环链表 。
对于双向循环列表，你可以将左右孩子指针作为双向循环链表的前驱和后继指针，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。
特别地，我们希望可以 就地 完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中最小元素的指针。
示例 1：
输入：root = [4,2,5,1,3]
输出：[1,2,3,4,5]
解释：下图显示了转化后的二叉搜索树，实线表示后继关系，虚线表示前驱关系。
示例 2：
输入：root = [2,1,3]
输出：[1,2,3]
示例 3：
输入：root = []
输出：[]
解释：输入是空树，所以输出也是空链表。
示例 4：
输入：root = [1]
输出：[1]
提示：
思路：
题目要求转换为 排序，双向循环链表。
1、排序：二叉搜索树的中序遍历有序，从小到大排序。
2、双向：构建相邻节点，前驱为pre，当前为cur，pre.right = cur; cur.left = pre; 。
3、循环：头节点head、尾节点tail，构建head.left = tail； tail.right = head; 。
这用了中序遍历，附下递归模板：
// V1
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new LinkedList<Integer>();
if(root==null) return result;
result.addAll(inorderTraversal(root.left)); // pre.addAll()
result.add(root.val);
result.addAll(inorderTraversal(root.right));
return result;
}
// V2
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new LinkedList<Integer>();
preHelper(root, result);
return result;
}
public void preHelper(TreeNode root, List<Integer> result) {
if(root==null) return;
preHelper(root.left, result);
result.add(root.val);
preHelper(root.right, result);
}
代码：
class Solution {
Node pre, head;
public Node treeToDoublyList(Node root) {
if(root == null) return null;
dfs(root);
head.left = pre;
pre.right = head;
return head;
}
private void dfs(Node cur) {
// 1-Terminator
if(cur == null) return;
// 4-Drill down：递归遍历左子树
dfs(cur.left);
// 2-Current logic：若节点pre不空，pre只赋值一次
if(pre != null) pre.right = cur;
// 若节点pre空，pre只赋值一次
else head = cur;
// 上一步连接两个节点 pre-->cur, 本步 pre<--cur
cur.left = pre;
// 移动：pre移到下一个节点
pre = cur;
// 4-Drill down
dfs(cur.right);
}
}
时间复杂度：
O
(
n
)
O(n)
O(n)
空间复杂度：
O
(
n
)
O(n)
O(n)
思路：
这其实算二叉树中序遍历（迭代版）的变形。
附两个二叉树中序遍历的迭代版本：
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode p = root;
while(!stack.isEmpty() || p != null) {
if(p != null) {
stack.push(p);
p = p.left;
} else {
TreeNode node = stack.pop();
result.add(node.val); // Add after all left children
p = node.right;
}
}
return result;
}
代码：
class Solution {
Node head, pre;
public Node treeToDoublyList(Node root) {
if (root == null) return null;
Deque<Node> stack = new ArrayDeque<>();
Node p = root;
while(!stack.isEmpty() || p != null) {
if(p != null) {
stack.push(p);
p = p.left;
} else {
Node node = stack.pop();
if (pre == null) {
head = node;
} else { // 否则将当前节点与pre连接，同时移动pre
pre.right = node;
}
node.left = pre;
pre = node;
p = node.right;
}
}
head.left = pre;
pre.right = head;
return head;
}
}
时间复杂度：
O
(
n
)
O(n)
O(n)
空间复杂度：
O
(
n
)
O(n)
O(n)