1 | 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。 |
1 | 特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。 |
一.解题思路：
- 判空
- 定义一个全局的头指针head，一个全局的前一次遍历的指针pre
- 中序递归遍历root节点
- 递归终止条件：当前节点为空
- 递归遍历左子树，然后访问当前节点，当pre指针为空时，说明是访问的第一个节点，将head指向当前节点，如果不为空，则直接将pre的右指针指向cur，将cur的left指针指向pre
- 然后将当前节点赋值给pre给下一次递归使用
- 递归遍历右子树
- 递归结束，则head为头指针，pre为尾指针，将head的left指向最后一个pre，将pre的right指针指向head即可
- 最后返回head即可
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
52
/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val,Node _left,Node _right) {
val = _val;
left = _left;
right = _right;
}
};
*/
class Solution {
Node head; //头节点
Node pre; //当前遍历节点的前一个节点
public Node treeToDoublyList(Node root) {
if (root == null) return null;
midTraverse(root);
head.left = pre; //头节点的前驱指向最后一个遍历到的元素
pre.right = head; //最后一个遍历到的元素的后继指向头节点
return head;
}
public void midTraverse(Node root) {
if (root != null) {
midTraverse(root.left);
if (pre != null) { //当前节点的前驱指向前一个更小的节点，前一个更小节点的后继指向当前的节点
root.left = pre;
pre.right = root;
} else { //如果pre为空，那么该节点是链表的头节点
head = root;
}
pre = root;
midTraverse(root.right);
}
}
}
参考文献
1 | 作者：1234-52 |
