Recursion
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
| class Solution {
private static class NodeHolder {
private Node head;
private Node pre;
}
public Node treeToDoublyList(Node root) {
if (root == null) {
return null;
}
NodeHolder nodeHolder = new NodeHolder();
dfs(nodeHolder, root);
Node tail = nodeHolder.pre;
nodeHolder.head.left = tail;
tail.right = nodeHolder.head;
return nodeHolder.head;
}
private void dfs(NodeHolder nodeHolder, Node node) {
if (node == null) {
return;
}
dfs(nodeHolder, node.left);
if (nodeHolder.pre == null) {
nodeHolder.head = node;
} else {
node.left = nodeHolder.pre;
nodeHolder.pre.right = node;
}
nodeHolder.pre = node;
dfs(nodeHolder, node.right);
}
}
|
Iterate
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
| class Solution {
public Node treeToDoublyList(Node root) {
if (root == null) {
return null;
}
Stack<Node> stack = new Stack<>();
Node head = null, pre = null;
while (!stack.isEmpty() || root != null) {
while (root != null) {
stack.push(root);
root = root.left;
}
Node node = stack.pop();
if (head == null) {
head = node;
}
if (pre != null) {
pre.right = node;
node.left = pre;
}
pre = node;
root = node.right;
}
head.left = pre;
pre.right = head;
return head;
}
}
|
该题可以在遍历过程中修改指针是因为修改的当前节点的 left 指针，此指针在后续不会再使用，注意与 144. Binary Tree Preorder Traversal 区分。
References
剑指 Offer 36. 二叉搜索树与双向链表
426. Convert Binary Search Tree to Sorted Doubly Linked List