0x00 题目

在一个 m*n 的二维字符串数组中输出二叉树
行数 m 应当等于给定二叉树的 高度
列数 n 应当总是 奇数

根节点 的值（以字符串格式给出）应当放在可放置的第一行正中间
根节点所在的行与列会将剩余空间划分为 两部分（左下部分和右下部分）
你应该将 左子树 输出在 左下 部分，右子树 输出在 右下 部分
左下和右下部分应当有 相同的大小
即使一个子树为空而另一个非空
你不需要为空的子树输出任何东西
但仍需要为另一个子树留出足够的空间
然而，如果两个子树 都为空 则不需要为它们留出任何空间
每个 未使用 的空间应包含一个空的字符串""
使用相同的规则输出子树

粟子：
请添加图片描述

请添加图片描述

0x01 思路

树的 高度，决定有 几行
一行的个数，是 2 ^ n - 1
n 为树的高度

根节点在第一层的 中间
以根节点为分界点
左节点 在左边的 中间
右节点 在右边的 中间
可以使用 递归 方式
找到位置，填写数值

0x02 解法

语言：Swift

树节点：TreeNode

public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init() { self.val = 0; self.left = nil; self.right = nil; }
    public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
    public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
        self.val = val
        self.left = left
        self.right = right
    }
}

解法：

func printTree(_ root: TreeNode?) -> [[String]] {
    // 求树高度
    func depth(_ root: TreeNode?) -> Int {
        guard let root = root else { return 0 }
        let left = depth(root.left)
        let right = depth(root.right)
        return max(left, right) + 1
    }
    
    // 打印
    func print(_ root: TreeNode?, _ l: Int, _ r: Int, _ row: Int) {
        guard let root = root else { return }
        
        // 找到中间索引
        let mid = (l + r) / 2
        
        // 更新
        arr[row][mid] = "\(root.val)"
        
        // 递归左子树
        print(root.left, l, mid-1, row+1)
        
        // 递归右子树        
        print(root.right, mid+1, r, row+1)
    }
    
    // 高度
    let height = depth(root)
    
    // 宽度
    let width = Int(powf(2, Float(height)) - 1)
    
    // height 行 x width 列的二维数组
    let row = Array(repeating: "", count: width)
    var arr = Array(repeating: row, count: height)
    
    print(root, 0, width-1, 0)
    
    return arr
}