【题目描述】
给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
例如：
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其自底向上的层次遍历为：
[
[15,7],
[9,20],
[3]
]
【思路1】
1、使用队列 迭代实现
2、判断队列是否为空
3、内部循环的次数count 是当前队列的size
4、当当前节点的left节点不为空，加入队列
5、当当前节点right节点不为空，加入队列
6、内部循环遍历完毕，加入到res数组内
7、时间复杂度O(m*n) m为层 n为每层的结点个数
8、空间复杂度O(n)
代码实现：
func levelOrderBottom(_ root: TreeNode?) -> [[Int]] {
if root == nil { return [] }
var res = [[Int]]()
var queue = Queue<TreeNode?>.init()
queue.push(x: root)
while !queue.isEmpty() {
var nums = [Int]()
var count = queue.size()
while count > 0 {
let node = queue.pop()
nums.append(node?.val ?? 0)
count-=1
if let left = node?.left {
queue.push(x: left)
}
if let right = node?.right {
queue.push(x: right)
}
}
res.append(nums)
}
return res.reversed()
}
【思路2】
1、递归实现
2、代码略
