Skip to content

655. Print Binary Tree

  • Time: $O(h \cdot 2^h)$
  • Space: $O(h \cdot 2^h)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
 public:
  vector<vector<string>> printTree(TreeNode* root) {
    const int m = maxHeight(root);
    const int n = pow(2, m) - 1;
    vector<vector<string>> ans(m, vector<string>(n));
    dfs(root, 0, 0, ans[0].size() - 1, ans);
    return ans;
  }

 private:
  int maxHeight(TreeNode* root) {
    if (root == nullptr)
      return 0;
    return 1 + max(maxHeight(root->left), maxHeight(root->right));
  }

  void dfs(TreeNode* root, int row, int left, int right,
           vector<vector<string>>& ans) {
    if (root == nullptr)
      return;

    const int mid = (left + right) / 2;
    ans[row][mid] = to_string(root->val);
    dfs(root->left, row + 1, left, mid - 1, ans);
    dfs(root->right, row + 1, mid + 1, right, ans);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
  public List<List<String>> printTree(TreeNode root) {
    final int m = maxHeight(root);
    final int n = (int) Math.pow(2, m) - 1;
    List<List<String>> ans = new ArrayList<>();
    List<String> row = new ArrayList<>();

    for (int i = 0; i < n; ++i)
      row.add("");

    for (int i = 0; i < m; ++i)
      ans.add(new ArrayList<>(row));

    dfs(root, 0, 0, n - 1, ans);
    return ans;
  }

  private int maxHeight(TreeNode root) {
    if (root == null)
      return 0;
    return 1 + Math.max(maxHeight(root.left), maxHeight(root.right));
  }

  private void dfs(TreeNode root, int row, int left, int right, List<List<String>> ans) {
    if (root == null)
      return;

    final int mid = (left + right) / 2;
    ans.get(row).set(mid, Integer.toString(root.val));
    dfs(root.left, row + 1, left, mid - 1, ans);
    dfs(root.right, row + 1, mid + 1, right, ans);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
  def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:
    def maxHeight(root: Optional[TreeNode]) -> int:
      if not root:
        return 0
      return 1 + max(maxHeight(root.left), maxHeight(root.right))

    def dfs(root: Optional[TreeNode], row: int, left: int, right: int) -> None:
      if not root:
        return

      mid = (left + right) // 2
      ans[row][mid] = str(root.val)
      dfs(root.left, row + 1, left, mid - 1)
      dfs(root.right, row + 1, mid + 1, right)

    m = maxHeight(root)
    n = pow(2, m) - 1
    ans = [[''] * n for _ in range(m)]
    dfs(root, 0, 0, len(ans[0]) - 1)
    return ans