切换主题
N叉树的遍历
递归遍历
递归遍历N叉树的时间复杂度：O(n)；空间复杂度：O(n)。
前序遍历
节点访问顺序：
根 -> 遍历子节点（左 -> 右）并递归处理子节点。
JavaScript
const preorder = (root, ret = []) => {
if (!root) return ret
ret.push(root.val)
for (const node of root.children) {
preorder(node, ret)
}
return ret
}后序遍历
节点访问顺序：
遍历子节点（左 -> 右）并递归处理子节点 -> 根。
JavaScript
const postorder = (root, ret = []) => {
if (!root) return ret
for (const node of root.children) {
postorder(node, ret)
}
ret.push(root.val)
return ret
}迭代遍历
迭代遍历，即模拟后进（Array#push） 先出（Array#pop）的栈数据结构。
时间复杂度：O(n)；空间复杂度：O(n)。
前序遍历
节点访问顺序：
根 -> 遍历子节点（左 -> 右）并递归处理子节点；
节点压栈顺序：遍历子节点（右 -> 左）并压栈 -> 根。
JavaScript
const preorder = (root, ret = []) => {
if (!root) return ret
const stack = [root]
while (stack.length) {
// ==>节点出栈时即为操作时间点
const node = stack.pop()
// <==
ret.push(node.val)
let len = node.children.length
while (len--) stack.push(node.children[len])
}
return ret
}后序遍历
节点访问顺序：
遍历子节点（左 -> 右）并递归处理子节点 ->；
节点压栈顺序：根 -> 遍历子节点（右 -> 左）并压栈。
JavaScript
const postorder = (root, ret = []) => {
if (!root) return ret
const stack = [root]
while (stack.length) {
// ==>节点出栈时即为操作时间点
const node = stack.pop()
// <==
ret.unshift(node.val)
node.children && stack.push(...node.children)
}
return ret
}层序遍历
模拟先进（Array#push） 先出（Array#shift）的队列数据结构。
JavaScript
const levelOrder = (root, ret = []) => {
if (!root) return ret
const queue = [root]
while (queue.length) {
let [len, lvNodes] = [queue.length, []]
while (len--) {
// ==>节点出队时即为操作时间点
const node = queue.shift()
// <==
lvNodes.push(node.val)
node.children && queue.push(...node.children)
}
ret.push(lvNodes)
}
return ret
}