655 打印二叉树

一、小白翻译

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

  • 树的高度为 height ,行数 m 应等于 height + 1 。

  • 列数 n 应等于​​x​​ - 1 。

  • 将根节点放置在顶行的中间(更正式地说,位于位置 res[0][(n-1)/2] )。

  • 对于已放置在矩阵中位置 res[r][c] 的每个节点,将其左子节点放置在 res[r+1][c-2] 处,将其右子节点放置在 res[r+1][c+2] 处。

  • 继续此过程,直到树中的所有节点都已放置完毕。

  • 任何空单元格都应包含空字符串 “” 。

返回构造的矩阵 res 。

二、例子

小白水平理解面试经典题目LeetCode 655. Print Binary Tree【Tree】-LMLPHP
小白水平理解面试经典题目LeetCode 655. Print Binary Tree【Tree】-LMLPHP
限制条件
小白水平理解面试经典题目LeetCode 655. Print Binary Tree【Tree】-LMLPHP

这里是小白理解

这种题目我们首先把他进行下条件梳理
这时候黑长直女神过来问:小白,你这题怎么思考的啊?
小白内心镇定:小美,马上春天了,有机会一起去公园出大片吧?
小白水平理解面试经典题目LeetCode 655. Print Binary Tree【Tree】-LMLPHP
哦,不是,这道题咱们可以考虑下用递归算法 + 画图来辅助做题
这里我拿一个三层的树进行举例子。
小白水平理解面试经典题目LeetCode 655. Print Binary Tree【Tree】-LMLPHP
我们如果在这样画出来就更加直观的看出来每个值的位置。
[
 [“”, “”, “”, “1”, “”, “”, “”],
 [“”, “2”, “”, “”, “”, “3”, “”],
 [“4”, “”, “5”, “”, “”, “”, “”]
]

  • 首先,我们需要计算出二叉树的高度,以便确定矩阵的行数。
  • 然后,我们可以根据高度计算出矩阵的列数,即 2。
  • 接下来,我们可以使用递归的方法来遍历二叉树,并将每个节点的值填充到矩阵中。
  • 在递归过程中,我们需要根据当前节点的位置来计算其在矩阵中的行列号。
  • 对于每个节点,我们需要将其值填充到矩阵中,并将其左右子树分别递归地打印到矩阵的左右两部分。

小美:小伙子,可以啊,这不仅逻辑感人,阅读理解也有俩下子, 不过要是照的不美可有你好看了!

小白:没问题,谁叫为了“真爱”呢。

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

真正面试环节

面试官:你可以解答这道”融合链表“的题目吗,来看看你对二叉树结构的理解。

小白:嘿嘿,这不巧了么这不是

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

    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 655. Print Binary Tree【Tree】-LMLPHP

============================================================================
🍀🍀🍀🍀🍀🍀更多算法题解请看 面试数据结构与算法总结分类+leetcode目录【基础版】
编码道路漫漫,只要先看脚下的路,徐徐前进即可。

03-02 18:10