05 August 2008
在一个 m*n 的二维字符串数组中输出二叉树，并遵守以下规则：
行数 m 应当等于给定二叉树的高度。
列数 n 应当总是奇数。
根节点的值（以字符串格式给出）应当放在可放置的第一行正中间。根节点所在的行与列会将剩余空间划分为两部分（左下部分和右下部分）。你应该将左子树输出在左下部分，右子树输出在右下部分。左下和右下部分应当有相同的大小。即使一个子树为空而另一个非空，你不需要为空的子树输出任何东西，但仍需要为另一个子树留出足够的空间。然而，如果两个子树都为空则不需要为它们留出任何空间。
每个未使用的空间应包含一个空的字符串”“。
使用相同的规则输出子树。
如果到达树的末尾，即 root = null，直接返回。
确定当前节点所在的列 j=(l+r)/2j=(l+r)/2。将当前节点输出到数组 resres 的第 ii 行第 jj 列，即 res[i][j]res[i][j]。
递归调用 fill(res, root.left, i + 1, l, (l + r) / 2)，输出 rootroot 的左子树。
递归调用 fill(res, root.right, i + 1, (l + r + 1) / 2, r)，输出 rootroot 的右子树。
时间复杂度：O(h*2^h)，其中 h 是树的高度，填充长度为 h×(2 h−1) 的数组 resres。
空间复杂度：O(h*2^h)，数组 resres 的长度为 h * (2^h-1)。
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
public class Solution {
public List<List<String>> printTree(TreeNode root) {
int height = getHeight(root);
String[][] res = new String[height][(1 << height) - 1];
for (String[] arr : res)
Arrays.fill(arr, "");
List<List<String>> ans = new ArrayList<>();
fill(res, root, 0, 0, res[0].length);
for (String[] arr : res)
ans.add(Arrays.asList(arr));
return ans;
}
public void fill(String[][] res, TreeNode root, int i, int l, int r) {
if (root == null)
return;
res[i][(l + r) / 2] = "" + root.val;
fill(res, root.left, i + 1, l, (l + r) / 2);
fill(res, root.right, i + 1, (l + r + 1) / 2, r);
}
public int getHeight(TreeNode root) {
if (root == null)
return 0;
return 1 + Math.max(getHeight(root.left), getHeight(root.right));
}
}
BFS
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
53
54
55
56
57
58
59
60
61
62
63
64
public class Solution
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
class Params {
Params(TreeNode n, int ii, int ll, int rr) {
root = n;
i = ii;
l = ll;
r = rr;
}
TreeNode root;
int i, l, r;
}
public List < List < String >> printTree(TreeNode root) {
int height = getHeight(root);
System.out.println(height);
String[][] res = new String[height][(1 << height) - 1];
for (String[] arr: res)
Arrays.fill(arr, "");
List < List < String >> ans = new ArrayList < > ();
fill(res, root, 0, 0, res[0].length);
for (String[] arr: res)
ans.add(Arrays.asList(arr));
return ans;
}
public void fill(String[][] res, TreeNode root, int i, int l, int r) {
Queue < Params > queue = new LinkedList();
queue.add(new Params(root, 0, 0, res[0].length));
while (!queue.isEmpty()) {
Params p = queue.remove();
res[p.i][(p.l + p.r) / 2] = "" + p.root.val;
if (p.root.left != null)
queue.add(new Params(p.root.left, p.i + 1, p.l, (p.l + p.r) / 2));
if (p.root.right != null)
queue.add(new Params(p.root.right, p.i + 1, (p.l + p.r + 1) / 2, p.r));
}
}
public int getHeight(TreeNode root) {
Queue < TreeNode > queue = new LinkedList();
queue.add(root);
int height = 0;
while (!queue.isEmpty()) {
height++;
Queue < TreeNode > temp = new LinkedList();
while (!queue.isEmpty()) {
TreeNode node = queue.remove();
if (node.left != null)
temp.add(node.left);
if (node.right != null)
temp.add(node.right);
}
queue = temp;
}
return height;
}
}