【力扣】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

题解：

递归+双指针法：

// 时间复杂度：O(n)
// 空间复杂度：O(n)
func levelOrderBottom(root *TreeNode) [][]int {
	reverse := func(data [][]int) {
		left, right := 0, len(data)-1
		for left < right {
			data[left], data[right] = data[right], data[left]
			left++
			right--
		}
	}
	var result [][]int
	depth := 0
	var order func(node *TreeNode, depth int)
	order = func(node *TreeNode, depth int) {
		if node == nil {
			return
		}
		if len(result) == depth {
			result = append(result, []int{})
		}
		result[depth] = append(result[depth], node.Val)
		order(node.Left, depth+1)
		order(node.Right, depth+1)
	}
	order(root, depth)
	reverse(result)
	return result
}