问题Leetcode输出一棵m*n的二维字符串数组中的二叉树，并遵守如下规则：行数m应等于给定二叉树的高度.列数n应始终为奇数。根节点的值（以字符串形式给出）应放在第一条可放置行的中间。根节点的行和列将剩余空间分成两部分（左下和右下）。您应该在左下部分输出左子树，在右下部分输出右子树。左下角和右下角的部分应该具有相同的大小。即使一个子树为空，另一个不为空，你也不需要为空子树输出任何东西，但你仍然需要为另一个子树留出足够的空间。但是，如果两个子树都是空的，则不需要为它们留出空间。每个未使用的空间应包含一个空字符串“”。使用相同的规则输出子树。例1：输入：1/2输出：[["","1",""],["2","",""]]例2：输入：1/\23\4输出：[["","","","1","","",""],["","2","","","","3",""],["","","4","","","",""]]例3：输入：1/\25/3/4输出：[["","","","","","","","1","","","","","","",""]["","","","2","","","","","","","","5","","",""]["","3","","",""、""、""、""、""、""、""、""、""、""、""]["4"、""、""、""、""、""、""、""、""、""、""、""、""、""、""、""、""]]注：二叉树的高度在范围[1,10]。思路DFS先求二叉树的最大深度，然后构建一个二维矩阵。列数为2*depth-1，行数为depth。然后用DFS存储二叉树，将左右子树的节点值存储到对应的(start+end)/2的左右两侧。CodePython3#Definitionforabinarytreenode.#classTreeNode:#def__init__(self,x):#self.val=x#self.left=None#self.right=Noneclass解决方案：defprintTree(self,root:TreeNode)->List[List[str]]:#找到最大深度defmaxDepth(root):如果不是root:return0left=maxDepth(root.left)right=maxDepth(root.right)return1+max(left,right)depth=maxDepth(root)#二维矩阵宽度wid=2**depth-1res=[['']*widfor_inrange(depth)]#DFSdefdfs(root,depth,start,end):#当前根节点放在(start+end)/2的中间位置res[depth-1][(start+end)//2]=str(root.val)ifroot.left:dfs(root.left,depth+1,start,(start+end)//2)ifroot.right:dfs(root.right,depth+1,(start+end)//2,end)dfs(root,1,0,宽度)返回资源链接GitHub
