前言
博客好久没更新了，10月的末尾来水一篇。
正文
问题来源
本问题来自leetcode上的102题。
问题描述
给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果：
[
[3],
[9,20],
[15,7]
]
分析：
本人写的非递归Go代码如下：
func levelOrder(root *TreeNode) [][]int {
if nil == root {
return nil
}
ret := make([][]int, 0)
queue := make([]*TreeNode, 0)
queueTemp := make([]*TreeNode, 0)
queue = append(queue, root)
for 0 != len(queue) {
rowTemp := make([]int, 0)//清空
for i := 0; i < len(queue); i++ {
ele := queue[i]
rowTemp = append(rowTemp, ele.Val)
if nil != ele.Left {
queueTemp = append(queueTemp, ele.Left)
}
if nil != ele.Right {
queueTemp = append(queueTemp, ele.Right)
}
}
ret = append(ret, rowTemp)
queue = queueTemp
queueTemp = make([]*TreeNode, 0)
}
return ret
}
网上效率高的递归代码
func levelOrder(root *TreeNode) [][]int {
return levelOrderBy(root, 0, nil)
}
func levelOrderBy(root *TreeNode, level int, resu [][]int) [][]int {
if root == nil {
return resu
}
if off := level - len(resu); off >= 0 {
resu = append(resu, make([][]int, off+1)...)
}
resu[level] = append(resu[level], root.Val)
resu = levelOrderBy(root.Left, level+1, resu)
resu = levelOrderBy(root.Right, level+1, resu)
return resu
}
总结：
继续思考优化方案
结语
不要懒，多看多写。
