广度优先遍历 BFS
解题思路
实现代码
var postorder = function (root) {
const res = [];
if (root === null) return res;
const stack = [];
stack.push(root);
const visited = new Set();
while (stack.length) {
const node = stack[stack.length - 1];
// 出栈
/* 如果当前节点为叶子节点或者当前节点的子节点已经遍历过 */
if (node.children.length === 0 || visited.has(node)) {
stack.pop();
res.push(node.val);
continue;
}
// 入栈
for (let i = node.children.length - 1; i >= 0; --i) {
stack.push(node.children[i]);
}
visited.add(node);
}
return res;
};
广度优先遍历 BFS（反转前序遍历）
实现代码
var postorder = function (root) {
const res = [];
if (root === null) return res;
const stk = [];
stk.push(root);
while (stk.length) {
const node = stk.pop();
res.push(node.val);
node.children.forEach(item => {
stk.push(item);
});
}
return res.reverse();
};
深度优先遍历 DFS
实现代码
var postorder = function (root) {
const res = [];
const dfs = (root) => {
if (root === null) return;
root.children.forEach(item => {
dfs(item);
});
res.push(root.val);
};
dfs(root);
return res;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 589. N 叉树的前序遍历
上一篇
评论
