Given the root of a binary tree, construct a 0-indexedm x n string matrix res that represents a formatted layout of the tree. The formatted layout matrix should be constructed using the following rules:
The height of the tree is height and the number of rows m should be equal to height + 1.
The number of columns n should be equal to 2^height+1^ - 1.
Place the root node in the middle of the top row (more formally, at location res[0][(n-1)/2]).
For each node that has been placed in the matrix at position res[r][c], place its left child at res[r+1][c-2^height-r-1^] and its right child at res[r+1][c+2^height-r-1^].
Continue this process until all the nodes in the tree have been placed.
Any empty cells should contain the empty string "".
from leetcode_py import TreeNodeclass Solution: # Time: O(n + m * n) where n is the number of nodes and m is the tree height # Space: O(m * n) for the result matrix def print_tree(self, root: TreeNode[int] | None) -> list[list[str]]: def height(node: TreeNode[int] | None) -> int: if node is None: return -1 return 1 + max(height(node.left), height(node.right)) h = height(root) rows, cols = h + 1, 2 ** (h + 1) - 1 res: list[list[str]] = [[""] * cols for _ in range(rows)] if root is None: return res def place(node: TreeNode[int] | None, r: int, c: int) -> None: if node is None: return res[r][c] = str(node.val) place(node.left, r + 1, c - 2 ** (h - r - 1)) place(node.right, r + 1, c + 2 ** (h - r - 1)) place(root, 0, (cols - 1) // 2) return res
