@@ -0,0 +1,1624 @@
+// Solution runs:%0A// - height takes O(n) time and O(h) space in the worst case, where h is height and can be n%0A// - building array takes O(2%5En) time and O(2%5En) space %5Boutput%5D%0A// - print takes O(n) time and O(h) space in the worst case, where h is height and can be n%0A//%0A// Idea is calculating height and total number of nodes in %22perfect tree%22 as (2%5Eheight - 1) first,%0A// because, regardless of the tree structure, we have to fill all positions of perfect tree (some%0A// positions are %22%22). Then we simply traverse tree passing level and start/end position for each%0A// subtree.%0A//%0A/**%0A * Definition for a binary tree node.%0A * public class TreeNode %7B%0A *     int val;%0A *     TreeNode left;%0A *     TreeNode right;%0A *     TreeNode(int x) %7B val = x; %7D%0A * %7D%0A */%0Aclass Solution %7B%0A  public List%3CList%3CString%3E%3E printTree(TreeNode root) %7B%0A    int height = height(root);%0A    int len = (1 %3C%3C height) - 1;%0A    List%3CList%3CString%3E%3E res = new ArrayList%3CList%3CString%3E%3E();%0A    for (int i = 0; i %3C height; i++) %7B%0A      res.add(new ArrayList%3CString%3E());%0A      for (int j = 0; j %3C len; j++) %7B%0A        res.get(i).add(%22%22);%0A      %7D%0A    %7D%0A    print(root, 0, 0, len-1, res);%0A    return res;%0A  %7D%0A%0A  private int height(TreeNode root) %7B%0A    if (root == null) return 0;%0A    return 1 + Math.max(height(root.left), height(root.right));%0A  %7D%0A%0A  private void print(TreeNode root, int level, int start, int end, List%3CList%3CString%3E%3E res) %7B%0A    if (root == null %7C%7C start %3E end) return;%0A    int mid = (start + end) / 2;%0A    res.get(level).set(mid, %22%22 + root.val);%0A    print(root.left, level+1, start, mid-1, res);%0A    print(root.right, level+1, mid+1, end, res);%0A  %7D%0A%7D%0A

add solution