题目
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]
]
解题思路
递归层序遍历二叉树，递归返回时加入每一层的节点值集合
代码
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
var ret [][]int
func levelTravel(nodeArr []*TreeNode){
var nextNodeArr []*TreeNode
var valArr []int
len1 := len(nodeArr)
if 0 == len1 {
return
}
for i := 0; i < len1; i++ {
v := nodeArr[i]
if nil != v.Left {
nextNodeArr = append(nextNodeArr, v.Left)
}
if nil != v.Right {
nextNodeArr = append(nextNodeArr, v.Right)
}
valArr = append(valArr, v.Val)
}
fmt.Printf("valArr:%+v\n", valArr)
levelTravel(nextNodeArr)
ret = append(ret, valArr)
}
func levelOrderBottom(root *TreeNode) [][]int {
if nil == root {
return [][]int{}
}
ret = [][]int{}
nextNodeArr := []*TreeNode{root}
levelTravel(nextNodeArr)
return ret
}
