【二叉樹】二叉樹的層序周遊 II

0x00 題目

給定一個二叉樹

傳回其節點值 ​​

​自底向上​

​​ 的層序周遊

即按從葉子節點所在層到根節點所在的層

逐層 ​​

​從左向右​

​ 周遊

0x01 思路

先 ​

​自頂向下​

​​ 周遊

得到最終結果後

再把周遊的結果 ​​

​倒序​

​ 即可

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 levelOrderBottom(_ root: TreeNode?) -> [[Int]] {
    guard let root = root else { return [] }
    
    // 存放結果
    var res: [[Int]] = []
    // 存放節點
    var queue: [TreeNode] = [root]

    while !queue.isEmpty {
        // 存儲下一層節點
        var tmp: [TreeNode] = []
        
        // 存儲目前層的節點值
        var arr: [Int] = []

        while !queue.isEmpty {
            let node = queue.removeFirst()
            arr.append(node.val)
            
            // 收集下層節點
            if let left = node.left {
                tmp.append(left)
            }
            if let right = node.right {
                tmp.append(right)
            }
        }

        queue = tmp
        res.append(arr)
    }
    
    // 倒序
    res.reverse() 
    return res
}