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


  • 0
    J
    // 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)
                result.add(new ArrayList<String>());
                
                for(int j = 0; j < rowCount; j++)
                    result.get(i).add(""); 
            }
            
            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;
        }
    }
    

Log in to reply
 

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