1
class Solution {
2
  public List<List<String>> printTree(TreeNode root) {
3
    List<List<String>> res = new ArrayList();
4

5
    int height = getHeight(root);
6
    int row = height + 1;
7
    int column = (int) Math.pow(2, height + 1) - 1;
8

9
    for (int k = 0; k < row; k++) {
10
      List<String> list = new ArrayList();
11
      for (int i = 0; i < column; i++) {
12
        list.add("");
13
      }
14
      res.add(list);
15
    }
16

17
    int left = 0;
18
    int right = column - 1;
19
    int level = 0;
20
    print(res, left, right, level, root);
21

22
    return res;
23
  }
24

25
  public void print(List<List<String>> res, int left, int right, int level, TreeNode root) {
26
    if (root == null) return;
27
    int mid = left + (right - left) / 2;
28
    res.get(level).set(mid, String.valueOf(root.val));
29

30
    print(res, left, mid - 1, level + 1, root.left);
31
    print(res, mid + 1, right, level + 1, root.right);
32
  }
33

34
  public int getHeight(TreeNode root) {
35
    if (root == null) return -1;
36
    int left = getHeight(root.left);
37
    int right = getHeight(root.right);
38

39
    return Math.max(left, right) + 1;
40
  }
41
}