算法面试真题详解：输出二叉树

描述
按照以下规则在 m*n 二维字符串数组中打印二叉树：

1. 行号m应该等于给定二叉树的高度。
2. 列号n始终为奇数。
3. 根节点的值（以字符串格式）应该放在它可以放入的第一行的正中间。根节点所属的列和行将剩余空间分成两部分（左下部分和右下部分）。您应该在左下部分打印左子树，并在右下部分打印右子树。左下部和右下部应具有相同的大小。即使一个子树为空，而另一个子树不为空，你也不需要打印空子树，但仍然需要留出与另外一个子树一样大的空间。但是，如果两个子树都为空，那么您不需要为它们留出空间。
4. 每个未使用的空格应包含一个空字符串""。
5. 按照相同的规则打印所有子树。
6. 二叉树的高度在[1,10][1,10]范围内。

在线评测地址：领扣题库官网

样例1

输入:{1,2}
    1
   /
  2
输出:
 [["", "1", ""],
  ["2", "", ""]]

样例2

输入: {1,2,3,#,4}
    1
   / \
  2   3
   \
    4
输出:
 [["", "", "", "1", "", "", ""],
  ["", "2", "", "", "", "3", ""],
  ["", "", "4", "", "", "", ""]]

样例3：

输入:{1,2,5,3,#,#,#,4}
        1
       / \
      2   5
     / 
    3 
   / 
  4 
输出:
 [["",  "",  "", "",  "", "", "", "1", "",  "",  "",  "",  "", "", ""]
  ["",  "",  "", "2", "", "", "", "",  "",  "",  "",  "5", "", "", ""]
  ["",  "3", "", "",  "", "", "", "",  "",  "",  "",  "",  "", "", ""]
  ["4", "",  "", "",  "", "", "", "",  "",  "",  "",  "",  "", "", ""]]

算法：DFS

算法思路

• 输出到的矩阵的列数永远是奇数 -- 对于所有子树, 即原矩阵的子矩阵也是奇数. 因为是奇数时, 左右子树才能平分列数. 一棵高度为 height 的二叉树对应的矩阵是 height∗(2height−1)height∗(2height−1) 的.
• 先 dfs 确定二叉树的高度, 然后定义字符串二维数组. 再次 dfs 把每一个节点的值填入二维数组即可. 第二次 dfs 的过程中需要记录以下信息:
• 当前节点所在行, 列 -- 确定当前节点的值填入二维数组的哪个位置
• 当前节点的子树的宽度 -- 确定该节点的左右子节点该填入的位置
• 当前节点在 row, col, 宽度是 width 时, 其左右子树的宽度均为 width / 2 - 1 (宽度永远是奇数), 左右子节点所在列与 col 的距离相同, 都是宽度的一半.

• 总归, 两次dfs就可以解决这个问题.

  public class Solution {
  /**
   * @param root: the given tree
   * @return: the binary tree in an m*n 2D string array
   */
  public List<List<String>> printTree(TreeNode root) {
      List<List<String>> res = new LinkedList<>();
      int height = root == null ? 1 : getHeight(root);
      int rows = height, columns = (int) (Math.pow(2, height) - 1);
      List<String> row = new ArrayList<>();
      for (int i = 0; i < columns; i++) {
          row.add("");
      }
      for (int i = 0; i < rows; i++) {
          res.add(new ArrayList<>(row));
      }
      populateRes(root, res, 0, rows, 0, columns - 1);
      return res;
  }
  
  public void populateRes(TreeNode root, List<List<String>> res, int row, int totalRows, int i, int j) {
      if (row == totalRows || root == null) {
          return;
      }
      res.get(row).set((i + j) / 2, Integer.toString(root.val));
      populateRes(root.left, res, row + 1, totalRows, i, (i + j) / 2 - 1);
      populateRes(root.right, res, row + 1, totalRows, (i + j) / 2 + 1, j);
  }
  
  public int getHeight(TreeNode root) {
      if (root == null)
          return 0;
      return 1 + Math.max(getHeight(root.left), getHeight(root.right));
  }

  更多题解参考：九章官网solution