小白水平理解面试经典题目LeetCode 655. Print Binary Tree【Tree】

655 打印二叉树

一、小白翻译

给定二叉树的 root ，构造一个 0 索引的 m x n 字符串矩阵 res 来表示树的格式化布局。格式化布局矩阵应使用以下规则构建：

树的高度为 height ，行数 m 应等于 height + 1 。
列数 n 应等于x^height+1 - 1 。
将根节点放置在顶行的中间（更正式地说，位于位置 res[0][(n-1)/2] ）。
对于已放置在矩阵中位置 res[r][c] 的每个节点，将其左子节点放置在 res[r+1][c-2^height-r-1] 处，将其右子节点放置在 res[r+1][c+2^height-r-1] 处。
继续此过程，直到树中的所有节点都已放置完毕。
任何空单元格都应包含空字符串 “” 。

返回构造的矩阵 res 。

二、例子

在这里插入图片描述

限制条件

这里是小白理解

这种题目我们首先把他进行下条件梳理
这时候黑长直女神过来问：小白，你这题怎么思考的啊？
小白内心镇定：小美，马上春天了，有机会一起去公园出大片吧？
在这里插入图片描述
哦，不是，这道题咱们可以考虑下用递归算法 + 画图来辅助做题
这里我拿一个三层的树进行举例子。

我们如果在这样画出来就更加直观的看出来每个值的位置。
[
[“”, “”, “”, “1”, “”, “”, “”],
[“”, “2”, “”, “”, “”, “3”, “”],
[“4”, “”, “5”, “”, “”, “”, “”]
]

首先，我们需要计算出二叉树的高度，以便确定矩阵的行数。
然后，我们可以根据高度计算出矩阵的列数，即 2^height-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();}}