Print Binary Tree
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
heightand the number of rowsmshould be equal toheight + 1. - The number of columns
nshould be equal to2^(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 atres[r + 1][c - 2^(height - r - 1)]and its right child atres[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
"".
Return the constructed matrix res.
Example 1
1 / 2
Input
root = [1,2]Output
[["","1",""],["2","",""]]The root value 1 is placed in the middle of the top row, and its left child 2 is placed in the next row to the left.
Example 2
1
/ \
2 3
\
4Input
root = [1,2,3,null,4]Output
[["","","","1","","",""],["","2","","","","3",""],["","","4","","","",""]]The tree of height 2 is formatted into a 3 by 7 matrix with each node placed according to its row and column offset rules.
Constraints
- The number of nodes in the tree is in the range
[1, 2^10]. -99 <= Node.val <= 99- The depth of the tree will be in the range
[1, 10].