Given the root
of a binary tree, construct a 0-indexed m 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 rowsm
should be equal toheight + 1
. - The number of columns
n
should be equal to2height+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 atres[r+1][c-2height-r-1]
and its right child atres[r+1][c+2height-r-1]
. - Continue this process until all the nodes in the tree have been placed.
- Any empty cells should contain the empty string
""
.
Return the constructed matrix res
.
Example 1:
Input: root = [1,2]
Output:
[["","1",""],
["2","",""]]
Example 2:
Input: root = [1,2,3,null,4]
Output:
[["","","","1","","",""],
["","2","","","","3",""],
["","","4","","","",""]]
Constraints:
- The number of nodes in the tree is in the range
[1, 210]
. -
-99 <= Node.val <= 99
- The depth of the tree will be in the range
[1, 10]
.
SOLUTION:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def getHeight(self, root):
if root:
return 1 + max(self.getHeight(root.left), self.getHeight(root.right))
return 0
def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:
h = self.getHeight(root)
cols = (1 << h) - 1
rows = h
op = [["" for i in range(cols)] for j in range(rows)]
nodes = [(root, 0, 0, cols)]
while len(nodes) > 0:
curr, l, a, b = nodes.pop()
if curr:
i = (a + b) // 2
op[l][i] = str(curr.val)
nodes.append((curr.left, l + 1, a, i))
nodes.append((curr.right, l + 1, i, b))
return op
Top comments (0)