1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
# 655. Print Binary Tree
from leetcode import treenode_build
"""
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 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]'). 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'.
"""
class Solution(object):
def printTree(self, root):
"""
:type root: Optional[TreeNode]
:rtype: List[List[str]]
"""
def height(node):
return 0 if not node else 1 + max(height(node.left), height(node.right))
def build(node, row, left, right):
if not node:
return
mid = (left + right) / 2
self.grid[row][mid] = str(node.val)
build(node.left, row + 1, left, mid - 1)
build(node.right, row + 1, mid + 1, right)
h = height(root)
w = 2**h - 1
self.grid = [[""] * w for i in range(h)]
build(node=root, row=0, left=0, right=w - 1)
return self.grid
if __name__ == "__main__":
obj = Solution()
r1 = treenode_build(vals=[1, 2])
r2 = treenode_build(vals=[1, 2, 3, None, 4])
print(obj.printTree(r1))
print(obj.printTree(r2))
|