# [JAVA] Find height and run recursive function / T : O(N*LogN), S : O(N*LogN)

• ``````// f(1) = 1
// f(2) = 2 * 1 + 1
// f(3) = 2 * 2 + 2 + 1
// f(4) = 2^3 + 2^2 + 2 + 1
// f(N) = 2^(N-1) + ... + 1
// (2 - 1)f(N) = 2^N - 1 => f(N) = 2^N - 1
public class Solution {
public List<List<String>> printTree(TreeNode root) {
List<List<String>> result = new ArrayList<List<String>>();
int height = getHeight(root); // O(N)
int rowCount = (int)Math.pow(2, height) - 1; // 평균적으로 logN => height이라고 하면 N

for(int i = 0; i < height; i++){  // T : O(N * LogN)

for(int j = 0; j < rowCount; j++)
}

helper(result, 0, 0, rowCount, root);

return result;
}

public void helper(List<List<String>> result, int depth, int low, int high, TreeNode root){
int index = (low + high)/2;
if(root == null)
return;
result.get(depth).set(index, String.valueOf(root.val));
helper(result, depth+1, low, index-1, root.left);
helper(result, depth+1, index + 1, high, root.right);
}

public int getHeight(TreeNode root){
if(root == null)
return 0;

int left = getHeight(root.left);
int right = getHeight(root.right);

return (left > right) ? left+1 : right+1;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.