# LeetCode: 655. 输出二叉树¶

## 1、题目描述¶

输入:
1
/
2

[["", "1", ""],
["2", "", ""]]


输入:
1
/ \
2   3
\
4

[["", "", "", "1", "", "", ""],
["", "2", "", "", "", "3", ""],
["", "", "4", "", "", "", ""]]


输入:
1
/ \
2   5
/
3
/
4

[["",  "",  "", "",  "", "", "", "1", "",  "",  "",  "",  "", "", ""]
["",  "",  "", "2", "", "", "", "",  "",  "",  "",  "5", "", "", ""]
["",  "3", "", "",  "", "", "", "",  "",  "",  "",  "",  "", "", ""]
["4", "",  "", "",  "", "", "", "",  "",  "",  "",  "",  "", "", ""]]

• 注意: 二叉树的高度在范围 [1, 10] 中。

## 2、解题思路¶

• 首先获取二叉树的深度level
• 每一行的长度即为2^level -1
• 然后对每个节点进行赋值
• 这时候采取区间法，也就是当前节点管理的区间范围，该节点放到中间
如一共4层，每一层为15个


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def printTree(self, root: TreeNode) -> List[List[str]]:

def get_level(node):
if not node:
return 0

left = get_level(node.left)
right = get_level(node.right)
return max(left + 1, right + 1)

levels = get_level(root)

res = [["" for _ in range(2 ** levels - 1)] for _ in range(levels)]

def write_matrix(node, level, start, end):
if not node:
return

current = (start + end) // 2
res[level][current] = str(node.val)
write_matrix(node.left, level + 1, start, current - 1)
write_matrix(node.right, level + 1, current + 1, end)

res[0][(2 ** levels - 1) // 2] = str(root.val)
write_matrix(root, 0, 0, 2 ** levels - 2)
return res