655. Print Binary Tree

T: O(n)
S: O(n)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private record Step(TreeNode node, int level, int index){};
    public List<List<String>> printTree(TreeNode root) {
        List<List<String>> result = new ArrayList<>();
        int height = dfs(root) - 1; // this dfs cal max node counts, so height need to minus 1
        int width = (int)Math.pow(2, height+1)-1;
        for (int i = 0; i <= height; i++) {
            List<String> list = new ArrayList<>();
            for (int j = 0; j < width; j++) {
                list.add("");
            }
            result.add(list);
        }

        dfsPopulateResult(result, root, 0, width/2, height);
        return result;
    }
    private void dfsPopulateResult(List<List<String>> result, TreeNode node, int row, int col, int height) {
        if (row == result.size() || node == null) {
            return;
        }
        result.get(row).set(col, String.valueOf(node.val));

        int nextIndexOffset = (int)Math.pow(2, height-row-1);
        dfsPopulateResult(result, node.left, row+1, col - nextIndexOffset, height);
        dfsPopulateResult(result, node.right, row+1, col + nextIndexOffset, height);
    }
    private int dfs(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int left = dfs(node.left);
        int right = dfs(node.right);
        return Math.max(left, right)+1;
    }
}

/***
T: O(n)
S: O(n)

height = 1
rows = 2

col = 2^(1+1) - 1 = 3



BFS:
        Queue<Step> queue = new LinkedList<>();
        queue.offer(new Step(root, 0, width/2));

        while (!queue.isEmpty()) {
            Step cur = queue.poll();
            TreeNode curNode = cur.node;
            //System.out.println("cur.index="+cur.index);
            result.get(cur.level).set(cur.index, String.valueOf(curNode.val));

            int nextIndexOffset = (int)Math.pow(2, height-cur.level-1);
            if (curNode.left != null) {
                int nextIndex = cur.index - nextIndexOffset;
                queue.offer(new Step(curNode.left, cur.level+1, nextIndex));
            }
            if (curNode.right != null) {
                int nextIndex = cur.index + nextIndexOffset;
                queue.offer(new Step(curNode.right, cur.level+1, nextIndex));
            }
        }
        return result;
 */