class Solution {
    public List<List<String>> printTree(TreeNode root) {
        List<List<String>> res = new ArrayList<>(); 
        if(root == null){
            return res; 
        }
        int h = getH(root);
        int cols = (int)Math.pow(2, h) - 1; 
        // init 
        for(int i = 0; i < h; i++){
            List<String> sub = new ArrayList<>(); 
            for(int j = 0; j < cols; j++){
                sub.add("");
            }
            res.add(new ArrayList<>(sub)); 
        }
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        // left and right index bounds 
        Deque<int[]> indexs = new LinkedList<>();
        indexs.offer(new int[]{0, cols - 1}); 
        int pos = 0;
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i = 0; i < size; i++){
                TreeNode curr = queue.poll();
                int[] ins = indexs.poll();
                int left = ins[0];
                int right = ins[1];
                int mid = left + (right - left)/2;
                // skip the curr if null 
                if(curr == null) continue; 
                // update 
                res.get(pos).set(mid, String.valueOf(curr.val));
                queue.offer(curr.left);
                queue.offer(curr.right);
                indexs.offer(new int[]{left, mid - 1});
                indexs.offer(new int[]{mid + 1, right});
            }
            pos++;
        }
        return res; 
    }
    private int getH(TreeNode root){
        //base case 
        if(root == null){
            return 0;
        }
        int leftRes = getH(root.left);
        int rightRes = getH(root.right);
        return Math.max(leftRes, rightRes) + 1; 
    }
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla