N 叉树的前序遍历
递归
function preorder(root: Node | null): number[] {
const ret: number[] = []
const dfs = (root: Node | null) => {
if (root === null) return
ret.push(root.val)
root.children.forEach(node => {
dfs(node)
})
}
dfs(root)
return ret
}
迭代
forEach
还需要配置 reverse
使用,性能低。
function preorder(root: Node | null): number[] {
const ret: number[] = []
if (root === null) return ret
const stack: Node[] = [root]
while (stack.length) {
const node = stack.pop()!
ret.push(node.val)
for (let i = node.children.length - 1; i >= 0; i--) {
stack.push(node.children[i])
}
}
return ret
}