package leetcode;

import java.util.List;

/**
 * https://leetcode.com/problems/print-binary-tree/
 */
public class Problem655 {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }

        @Override
        public String toString() {
            return "" + val;
        }
    }

    public List<List<String>> printTree(TreeNode root) {
        // TODO
        return null;
    }

    private static void print(List<List<String>> list) {
        for (List<String> l : list) {
            System.out.println(l);
        }
    }

    public static void main(String[] args) {
        Problem655 prob = new Problem655();

        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        print(prob.printTree(root));

        root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.right = new TreeNode(4);
        print(prob.printTree(root));

        root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(5);
        root.left.left = new TreeNode(3);
        root.left.left.left = new TreeNode(4);
        print(prob.printTree(root));
    }
}

@@ -12,16 +12,44 @@
 tcode;%0A%0A
+import java.util.ArrayList;%0A
 import j
@@ -311,262 +311,257 @@
   %7D%0A
-%0A        @Override%0A        public String toString() %7B%0A            return %22%22 + val;%0A        %7D%0A    %7D%0A%0A    public List%3CList%3CString%3E%3E printTree(TreeNode root) %7B%0A        // TODO%0A        return null
+    %7D%0A%0A    public List%3CList%3CString%3E%3E printTree(TreeNode root) %7B%0A        List%3CList%3CString%3E%3E result = new ArrayList%3C%3E();%0A        int rowSize = height(root)
 ;%0A    
-%7D%0A%0A
     
-private static void print(List%3CList%3CString%3E%3E list
+int colSize = (int) Math.pow(2, rowSize) - 1;%0A        for (int i = 0; i %3C rowSize; i++
 ) %7B%0A
@@ -568,21 +568,20 @@
         
-for (
+    
 List%3CStr
@@ -589,54 +589,84 @@
 ng%3E 
-l : list) %7B%0A            System.out.println(l);
+newList = new ArrayList%3C%3E();%0A            for (int j = 0; j %3C colSize; j++) %7B
 %0A   
@@ -674,643 +674,910 @@
     
-%7D%0A
     
-%7D%0A%0A
     
-public static void main(String%5B%5D args) %7B%0A        Problem655 prob = new Problem655();%0A%0A        TreeNode root = new TreeNode(1);%0A        root.left = new TreeNode(2)
+newList.add(%22%22);%0A            %7D%0A            result.add(newList);%0A        %7D%0A        printTree(root, 0, 0, colSize - 1, result);%0A        return result
 ;%0A    
+%7D%0A%0A
     pri
-nt(prob.printTree(root));%0A%0A        root = new TreeNode(1);%0A        root.left = new TreeNode(2);%0A        root.right = new TreeNode(3);%0A        root.left.right = new TreeNode(4);%0A        print(prob.printTree(root)
+vate static void printTree(TreeNode node, int row, int colLeft, int colRight, List%3CList%3CString%3E%3E result) %7B%0A        if (node == null) %7B%0A            return;%0A        %7D%0A        int mid = (colLeft + colRight) / 2;%0A        result.get(row).set(mid, Integer.toString(node.val));%0A        printTree(node.left, row + 1, colLeft, mid - 1, result);%0A        printTree(node.right, row + 1, mid + 1, colRight, result
 );%0A
-%0A
     
+%7D%0A%0A
     
-root = new TreeNode(1);%0A        root.lef
+private static int height(TreeNode root) %7B%0A        if (roo
 t =
+=
  n
-ew TreeNode(2);%0A        root.right = new TreeNode(5);%0A        root.left.left = new TreeNode(3
+ull) %7B%0A            return 0;%0A        %7D%0A        return 1 + Math.max(height(root.left), height(root.right)
 );%0A    
+%7D%0A%0A
     
-root.left.left.left = new TreeNode(4);%0A        print(prob.printTree(root));
+private static void print(List%3CList%3CString%3E%3E list) %7B%0A        for (List%3CString%3E l : list) %7B%0A            System.out.println(l);%0A        %7D
 %0A   

Solve problem 655