写点什么

LeetCode 题解:589. N 叉树的前序遍历,栈,JavaScript,详细注释

用户头像
Lee Chen
关注
发布于: 2020 年 10 月 16 日
LeetCode题解:589. N叉树的前序遍历,栈,JavaScript,详细注释

原题链接:https://leetcode-cn.com/problems/n-ary-tree-preorder-traversal/


解题思路:


该题与144. 二叉树的前序遍历的解题思路类似,可以参考我的题解[LeetCode 题解:144. 二叉树的前序遍历,使用栈,JavaScript,详细注释](https://leetcode-cn.com/problems/binary-tree-preorder-traversal/solution/leetcodeti-jie-144-er-cha-shu-de-qian-xu-bian-li-s/)


  1. 前序遍历的顺序为,从上到下,从左到右,优先从左向下。

  2. 使用栈来遍历元素,每次循环都将栈顶元素的值存入结果。

  3. 同时从右向左遍历当前元素的子节点,这样就保证了出栈时的从上到下,从左到右,优先从左向下顺序。


/**
* @param {Node} root
* @return {number[]}
*/
var preorder = function (root) {
let result = []; // 保存遍历结果
let stack = []; // 使用栈遍历
root && stack.push(root); // 将根节点存入栈,开始遍历
// 在遍历过程中会不断有元素入栈,栈为空时遍历完成。
while (stack.length) {
// 弹出栈顶元素,此为当前遍历结果
const node = stack.pop();
result.push(node.val);
// 如果子节点存在,才继续遍历
if (node.children) {
// 每次遍历节点时,都将当前节点的子节点入栈,保证了从上到下的遍历顺序。
// 将子节点从右向左入栈,保证了从左到右的出栈顺序。
// 同时,每次都是左侧的子节点优先出栈,保证了优先从左向下的顺序。
for (let i = node.children.length - 1; i >= 0; i--) {
stack.push(node.children[i]);
}
}
}
return result;
};
复制代码


发布于: 2020 年 10 月 16 日阅读数: 33
用户头像

Lee Chen

关注

还未添加个人签名 2018.08.29 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode题解:589. N叉树的前序遍历,栈,JavaScript,详细注释