友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
655. 输出二叉树
给你一棵二叉树的根节点 root，请你构造一个下标从 0 开始、大小为 m x n 的字符串矩阵 res，用以表示树的 格式化布局。构造此格式化布局矩阵需要遵循以下规则：
-
树的 高度 为
height，矩阵的行数m应该等于height + 1。 -
矩阵的列数
n应该等于2height+1 - 1+。 -
根节点 需要放置在 顶行 的 正中间 ，对应位置为
res[0][(n-1)/2]。 -
对于放置在矩阵中的每个节点，设对应位置为
res[r][c]，将其左子节点放置在res[r+1][c-2height-r-1]，右子节点放置在res[r+1][c+2height-r-1]。 -
继续这一过程，直到树中的所有节点都妥善放置。
-
任意空单元格都应该包含空字符串
""。
返回构造得到的矩阵 res。
示例 1：
输入：root = [1,2] 输出： [["","1",""], ["2","",""]]
示例 2：
输入：root = [1,2,3,null,4] 输出： [["","","","1","","",""], ["","2","","","","3",""], ["","","4","","","",""]]
提示：
-
树中节点数在范围
[1, 210]内 -
-99 <= Node.val <= 99 -
树的深度在范围
[1, 10]内
思路分析
深度优先遍历。题目理解起来有些拗口！重新描述一下，就是每次都把节点值添加到当前范围的整中间。其余填空字符串。
-
一刷
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
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2026-04-22 21:49:32
*/
public List<List<String>> printTree(TreeNode root) {
int height = getHeight(root);
int m = height + 1;
List<String[]> data = new ArrayList<>(m);
int n = (1 << (height + 1)) - 1;
dfs(data, height, root, 0, 0, n - 1);
List<List<String>> result = new ArrayList<>();
for (String[] datum : data) {
List<String> row = new ArrayList<>(n);
for (String s : datum) {
row.add(Objects.isNull(s) ? "" : s);
}
result.add(row);
}
return result;
}
private void dfs(List<String[]> data, int height, TreeNode root,
int index, int left, int right) {
if (Objects.isNull(root)) {
return;
}
String[] r;
if (data.size() == index) {
r = new String[(1 << (height + 1)) - 1];
data.add(r);
} else {
r = data.get(index);
}
// 每次都在中间位置添加元素
int mid = left + (right - left + 1) / 2;
r[mid] = String.valueOf(root.val);
dfs(data, height, root.left, index + 1, left, mid - 1);
dfs(data, height, root.right, index + 1, mid + 1, right);
}
private int getHeight(TreeNode root) {
if (Objects.isNull(root)) {
return -1;
}
return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
}