Skip to content

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

@chencl1986

Description

@chencl1986

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

解题思路:

该题与144. 二叉树的前序遍历的解题思路类似,可以参考我的题解LeetCode题解:144. 二叉树的前序遍历,使用栈,JavaScript,详细注释

  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;
};

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions