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
| class Solution {
private Node head, tail;
public Node treeToDoublyList(Node root) {
if (root == null) {
return null;
}
Node[] headTailPair = helper(root);
headTailPair[0].left = headTailPair[1];
headTailPair[1].right = headTailPair[0];
return headTailPair[0];
}
private Node[] helper(Node node) {
if (node == null) {
return new Node[] { null, null };
}
Node[] leftTree = helper(node.left);
Node[] rightTree = helper(node.right);
Node[] ans = new Node[] { node, node };
if (leftTree[1] != null) {
node.left = leftTree[1];
leftTree[1].right = node;
ans[0] = leftTree[0];
}
if (rightTree[0] != null) {
node.right = rightTree[0];
rightTree[0].left = node;
ans[1] = rightTree[1];
}
return ans;
}
}
|
递归函数干的事情就是把给定的树变成DLL但是首位不相接并且把处理好的链表的头尾以数组的形式给我们.
时间复杂度: O(n)
空间复杂度: O(n) 一个是递归, 还有就是每个node返回的时候都会分配一个长度为2的数组.
第15, 16行如果不想在遇到null的时候分配两个null数组, 可以看下面的这个解法. 就是只有在左支或者右支不是null的时候再去调用递归函数. 时间复杂度和空间复杂度不变.
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 {
private Node head, tail;
public Node treeToDoublyList(Node root) {
if (root == null) {
return null;
}
Node[] headTailPair = helper(root);
headTailPair[0].left = headTailPair[1];
headTailPair[1].right = headTailPair[0];
return headTailPair[0];
}
private Node[] helper(Node node) {
Node[] leftTree = null, rightTree = null;
if (node.left != null) {
leftTree = helper(node.left);
}
if (node.right != null) {
rightTree = helper(node.right);
}
Node[] ans = new Node[] { node, node };
if (leftTree != null) {
node.left = leftTree[1];
leftTree[1].right = node;
ans[0] = leftTree[0];
}
if (rightTree != null) {
node.right = rightTree[0];
rightTree[0].left = node;
ans[1] = rightTree[1];
}
return ans;
}
}
|
