算法面試真題詳解：輸出二叉樹

描述

按照以下規則在 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