Skip to main content

102. Binary Tree Level Order Traversal

分析

1. dfs + 层记录
2. 队列模拟

用 go 写的时候翻了个错误,copy(a, b),copy 的长度会根据 通过字面量无初值创建的切片,长度为0

It returns the number of elements copied, which will be the minimum of len(dst) and len(src).

题解

var levelOrder = function(root) {
if(!root) {
return []
}
const ans = []
const dfs = (level, node) => {
if(!ans[level]) {
ans[level] = []
}
ans[level].push(node.val)
node.left && dfs(level + 1, node.left)
node.right && dfs(level + 1, node.right)
}

dfs(0, root)

return ans
};
func levelOrder(root *TreeNode) [][]int {
if root == nil {
return [][]int{}
}

queue := []*TreeNode{
root,
}

ans := [][]int{}

for len(queue) != 0 {
currentLevelAns := []int{}
currentLevelQueue := make([]*TreeNode, len(queue))
copy(currentLevelQueue, queue)
queue = []*TreeNode{}
for len(currentLevelQueue) != 0 {
first := currentLevelQueue[0]
currentLevelAns = append(currentLevelAns, first.Val)
if first.Left != nil {
queue = append(queue, first.Left)
}
if first.Right != nil {
queue = append(queue, first.Right)
}
currentLevelQueue = currentLevelQueue[1:]
}
ans = append(ans, currentLevelAns)
}
return ans
}