107. 二叉树的层序遍历 II

题目#

给定一个二叉树，返回其节点值自底向上的层序遍历。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

例如：给定二叉树 [3,9,20,null,null,15,7],

返回其自底向上的层序遍历为：

[
  [15,7],
  [9,20],
  [3]
]

思路#

本质还是层序遍历。

类似于 103. 二叉树的锯齿形层序遍历，不过是一个整体的 reverse。

代码#

func levelOrderBottom(root *TreeNode) [][]int {
    result := [][]int{}
    if root == nil {
        return result
    }

    queue := []*TreeNode{}
    queue = append(queue, root)
    for len(queue) > 0 {
        level := []int{}
        l := len(queue)
        for i := 0; i < l; i++ {
            n := queue[0]
            queue = queue[1:]

            level = append(level, n.Val)
            if n.Left != nil {
                queue = append(queue, n.Left)
            }
            if n.Right != nil {
                queue = append(queue, n.Right)
            }
        }
        result = append(result, level)
    }
    // 上面是普普通通的层序遍历
    // 下面是 reverse 操作
    for i := 0; i < len(result)/2; i++ {
        result[i], result[len(result)-1-i] = result[len(result)-1-i], result[i]
    }

    return result
}