655 打印二叉树
一、小白翻译
给定二叉树的 root ，构造一个 0 索引的 m x n 字符串矩阵 res 来表示树的格式化布局。格式化布局矩阵应使用以下规则构建：
-
树的高度为 height ，行数 m 应等于 height + 1 。
-
列数 n 应等于xheight+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”, “”, “”, “”],
[“”, “2”, “”, “”, “”, “3”, “”],
[“4”, “”, “5”, “”, “”, “”, “”]
]
- 首先，我们需要计算出二叉树的高度，以便确定矩阵的行数。
- 然后，我们可以根据高度计算出矩阵的列数，即 2height-1。
- 接下来，我们可以使用递归的方法来遍历二叉树，并将每个节点的值填充到矩阵中。
- 在递归过程中，我们需要根据当前节点的位置来计算其在矩阵中的行列号。
- 对于每个节点，我们需要将其值填充到矩阵中，并将其左右子树分别递归地打印到矩阵的左右两部分。
小美：小伙子，可以啊，这不仅逻辑感人，阅读理解也有俩下子, 不过要是照的不美可有你好看了！
小白：没问题，谁叫为了“真爱”呢。
真正面试环节
面试官：你可以解答这道”融合链表“的题目吗，来看看你对二叉树结构的理解。
小白：嘿嘿，这不巧了么这不是
public List<List<String>> printTree(TreeNode root) {
int height = getHeight(root); // 树的高度
int width = (1 << height) - 1; // 总的列数
List<List<String>> res = new ArrayList<>();
// 给出整个矩阵
for (int i = 0; i < height; i++) {
List<String> row = new ArrayList<>();
for (int j = 0; j < width; j++) {
row.add("");
}
res.add(row);
}
printTree(root, res, 0, 0, width - 1);
return res;
}
// 算出树高度
private int getHeight(TreeNode root) {
if (root == null) {
return 0;
}
return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
}
private void printTree(TreeNode root, List<List<String>> res, int row, int start, int end) {
if (root == null) {
return;
}
int mid = (start + end) / 2;
res.get(row).set(mid, String.valueOf(root.val));
// 对左侧子树进行计算
printTree(root.left, res, row + 1, start, mid - 1);
// 对右侧子树进行计算
printTree(root.right, res, row + 1, mid + 1, end);
}
这里的宽度采用了位运算
为了不熟悉位运算的，这里用个例子便于大家理解。
1 << 3 代表的意思是 “1的二进制数左移3项”
0001 1000
1 8
小明：OK，完事儿，等着面试官来表扬自己吧。他肯定会说：小子，你是个好手！工位都给你准备好了，工资你说了算。
面试官：矮油，不错啊，不过你这能不能写个测试啊。
小明OS：今年这个找工市场，人言洛阳花似锦，偏我来时不逢春。。。不是，怎么还让我些test case 啊！
总结
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
printBinaryTree655 solution = new printBinaryTree655();
List<List<String>> res = solution.printTree(root);
for (List<String> row : res) {
for (String s : row) {
System.out.print(s + " ");
}
System.out.println();
}
}
小白：您好，面试官，这回可以了吧，我终于可以开心练摄影技术为小美照相了！
============================================================================
🍀🍀🍀🍀🍀🍀更多算法题解请看 面试数据结构与算法总结分类+leetcode目录【基础版】
编码道路漫漫，只要先看脚下的路，徐徐前进即可。
