GaoLi's Blog

N叉树的常见遍历算法

如图给定一个 N 叉树,返回其节点值的遍历。假设节点的结构如下:

1
2
3
4
interface INode {
val: number;
children?: INode[];
}

前序遍历

预期遍历结果:[1,3,5,6,2,4]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function preorder(root: INode | null): number[] {
let result: number[] = [];

if (!root) {
return [];
}

const { val, children = [] } = root;

result.push(val);

children.forEach((child) => {
result = result.concat(preorder(child));
});

return result;
}

后序遍历

预期遍历结果:[5,6,3,2,4,1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function postorder(root: INode | null): number[] {
let result: number[] = [];

if (!root) {
return [];
}

const { val, children = [] } = root;

children.forEach((child) => {
result = result.concat(postorder(child));
});

result.push(val);

return result;
}

层序遍历

预期遍历结果:[[1],[3,2,4],[5,6]]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function levelOrder(root: INode | null): number[][] {
const result: number[][] = [];

if (!root) {
return [];
}

const traversal = function (node: INode, depth: number) {
if (!result[depth]) {
result[depth] = [];
}

const { val, children = [] } = node;

result[depth].push(val);

children.forEach((child) => {
traversal(child, depth + 1);
});
};

traversal(root, 0);

return result;
}