107. 二叉树的层序遍历 II

题目

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

难度：🌟🌟🌟

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[15,7],[9,20],[3]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

• 树中节点数目在范围 [0, 2000] 内
• -1000 <= Node.val <= 1000

题解

这题和 102. 二叉树的层序遍历思路是一样的，自顶向下的层序遍历反过来就行。

代码实现

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func levelOrderBottom(root *TreeNode) [][]int {
	if root == nil {
		return nil
	}
	var res [][]int
	queue := newQueue()
	queue.offer(root)
	for !queue.isEmpty() {
		sz := queue.len()
		var ans []int
		for sz > 0 {
			node := queue.pop()
			ans = append(ans, node.Val)
			if node.Left != nil {
				queue.offer(node.Left)
			}
			if node.Right != nil {
				queue.offer(node.Right)
			}
			sz--
		}
		res = append(res, ans)
	}
	// 交换 res 数组顺序
	n := len(res)
	for i := 0; i < n/2; i++ {
		tmp := res[n-i-1]
		res[n-i-1] = res[i]
		res[i] = tmp
	}
	return res
}

type myQueue struct {
	data []*TreeNode
}

func newQueue() *myQueue {
	return &myQueue{}
}

func (q *myQueue) offer(elem *TreeNode) {
	q.data = append(q.data, elem)
}

func (q *myQueue) pop() *TreeNode {
	res := q.data[0]
	q.data = q.data[1:]
	return res
}

func (q *myQueue) len() int {
	return len(q.data)
}

func (q *myQueue) isEmpty() bool {
	return q.len() == 0
}