输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
为了让您更好地理解问题，以下面的二叉搜索树为例：
我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。
下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。
特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解：
这道题考的是， 二叉树的中序遍历 以及 双向链表的相关操作
- 中序遍历二叉树
- 使用三个指针
- cur指针用来遍历节点
- pre指针指向 cur 的前一个节点
- head指针为新链表的头节点
- 遍历二叉树时
- 如果是访问的第一个节点
- 则为链表的头节点 head = cur
- cur.left = pre
- pre = cur
- 如果访问的不是第一个节点(此时 pre 不为空)
- pre.right = cur
- cur.left = pre
- pre = cur
- 依次遍历所有节点，当遍历到最后一个节点时，结束遍历
- 此时 head 为中序遍历的第一个节点，即链表的****头节点，
- pre为 中序遍历最后一个节点，即链表的尾节点
- 所以中序遍历完毕以后，我们再将 pre 和 head串起来
- pre.right = head;
- head.left = pre
- 然后返回 head 即可.
模拟过程如下 :
代码
- 有了思路以后，题目就变得简单了，无非是 dfs二叉树，以及一些链表的基本操作而已
思路一 ： 递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
/**
* 观察题目
* 可以看出，二叉搜索树转为双向链表之后，为二叉树中序遍历的结果
* 所以 dfs中序遍历二叉树
* <p>
* 记录 pre指针 和 head指针
* pre表示 当前节点的 上一个
* head表示 头节点
*
* dfs 深度优先遍历 中序遍历
* 当 pre 为空时， 为第一次遍历，头节点设置成 cur, 且把node.left = pre.pre = cur
* 当 pre 不为空时, 不是第一次遍历，把pre 和 cur串起来，之后pre = cur
*/
Node pre = null, head = null;
public Node treeToDoublyList1(Node root) {
if (root == null) return null;
// dfs
dfs(root);
// 最后 head 为头节点， pre 为尾节点， 把head 和 pre串起来
head.left = pre;
pre.right = head;
// head 就是链表当头节点
return head;
}
// 递归
void dfs(Node cur) {
if (cur == null) return;
dfs(cur.left);
if (pre != null) {
// 当 pre 不为空时, 不是第一次遍历，把pre 和 cur串起来，之后pre = cur
pre.right = cur;
} else {
// 为第一次遍历，头节点设置成 cur, 且把node.left = pre.pre = cur
head = cur;
}
cur.left = pre;
pre = cur;
dfs(cur.right);
}
|
思路二： 迭代
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
/**
* 观察题目
* 可以看出，二叉搜索树转为双向链表之后，为二叉树中序遍历的结果
* 所以 dfs中序遍历二叉树
* <p>
* 记录 pre指针 和 head指针
* pre表示 当前节点的 上一个
* head表示 头节点
*
* dfs 深度优先遍历 中序遍历
* 当 pre 为空时， 为第一次遍历，头节点设置成 cur, 且把node.left = pre.pre = cur
* 当 pre 不为空时, 不是第一次遍历，把pre 和 cur串起来，之后pre = cur
*/
Node pre = null, head = null;
public Node treeToDoublyList1(Node root) {
if (root == null) return null;
// dfs
inorderTraversal(root);
// 最后 head 为头节点， pre 为尾节点， 把head 和 pre串起来
head.left = pre;
pre.right = head;
// head 就是链表当头节点
return head;
}
// 迭代
void inorderTraversal(Node cur){
Stack<Node> stack = new Stack<>();
while (!stack.isEmpty() || cur != null){
while (cur != null){
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
if (pre != null){
pre.right = cur;
}else {
head = cur;
}
cur.left = pre;
pre = cur;
cur = cur.right;
}
}
|
复杂度分析 :
时间复杂度 : O(N) 其中N位树元素数量，遍历树的所有节点
空间复杂度 : O(N) 最差情况二叉搜索树退化成链表。
- 递归深度达到 O(N), 使用 O(N) 栈空间。
- 非递归调用，也使用了额外的 O(N) 的 Stack额外存储.