Print Binary Tree
按照要求输出二叉树在对应二维数组种的值
/**
* Definition for a binary tree node.
* public class TreeNode {
* public var val: Int
* public var left: TreeNode?
* public var right: TreeNode?
* public init(_ val: Int) {
* self.val = val
* self.left = nil
* self.right = nil
* }
* }
*/
class Solution {
func printTree(_ root: TreeNode?) -> [[String]] {
let height = getHeight(root);
let width = 1<<height - 1
var ans = Array(repeating: Array(repeating: "", count: width), count: height)
fill(root, ans: &ans, h: 0, l: 0, r: width - 1)
return ans
}
// 递归获取二叉树的高度 如果二叉树的右字数为空 则当前高度为 1 .. 反之.. 最后求得最大的左右字数的高度 + 1
func getHeight(_ root: TreeNode?) -> Int {
guard let r = root else { return 0 }
return max(getHeight(r.left), getHeight(r.right)) + 1
}
// 递归填充结果数组
func fill(_ root: TreeNode?, ans: inout [[String]], h: Int, l: Int, r: Int) -> [[String]] {
guard let ro = root else { return ans }
let mid = (l + r) / 2
ans[h][mid] = "\(ro.val)"
fill(ro.left, ans: &ans, h: h + 1, l: l, r: mid - 1)
fill(ro.right, ans: &ans, h: h + 1, l: mid + 1, r: r)
return ans
}
}
