## Tree - 107. Binary Tree Level Order Traversal II

Published on with 0 views and 0 comments

107. Binary Tree Level Order Traversal II

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).

For example:
Given binary tree `[3,9,20,null,null,15,7]`,

``````    3
/ \
9  20
/  \
15   7

``````

return its bottom-up level order traversal as:

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

go：

``````/**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func levelOrderBottom(root *TreeNode) [][]int {
var res, out [][]int
if root == nil {return out}

var curQ = []*TreeNode{root}
var nextQ []*TreeNode
var level []int

for len(curQ) != 0 {
for len(curQ) != 0 {
cur := curQ[0]
curQ = curQ[1:]
level = append(level, cur.Val)
if cur.Left != nil {
nextQ = append(nextQ, cur.Left)
}
if cur.Right != nil {
nextQ = append(nextQ, cur.Right)
}
}
curQ = nextQ
nextQ = nil
out = append(out, level)
level = nil
}

for i := len(out) -1; i >= 0; i-- {
res = append(res, out[i])
}
return res
}
``````