0655. Print Binary Tree¶
题目信息¶
- 题号:
0655
- 难度:
Medium
- 主题:
二叉树、二维字符串矩阵、层级布局、居中定位
- 原题:
- 重点:
矩阵尺寸由树高唯一决定、根节点置于首行中央、左右孩子递归放在各自区间中央、空位置使用空字符串
题目重述¶
给定非空二叉树根节点 root,构造一个零基二维字符串矩阵来展示树。设树高 height 为根到最深叶子的边数,则矩阵行数 m = height + 1,列数 n = 2^(height + 1) - 1。
根节点的十进制字符串放在 res[0][(n-1)/2]。若节点位于 res[r][c],其左孩子放在下一行向左偏移 2^(height-r-1) 的位置,右孩子放在对称的右侧位置;不存在节点的格子保持 ""。树中节点数位于 [1, 1024],树高不超过 10。
自建示例¶
根节点有两个孩子:
输入:root = [1,2,3]
输出:[["","1",""],["2","","3"]]
解释:树高为 1,因此矩阵为 2 行 3 列;根位于首行中央,左右孩子位于下一行两端。
只有连续左孩子:
输入:root = [4,2,null,1]
输出:[["","","","4","","",""],["","2","","","","",""],["1","","","","","",""]]
解释:树高为 2,矩阵有 7 列;每个左孩子都放在其父节点负责区间的中央位置。