590. N 叉树的后序遍历

题目

给定一个 N 叉树，返回其节点值的 后序遍历 。

N 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。

题解

递归

/**
 * // Definition for a Node.
 * function Node(val,children) {
 *    this.val = val;
 *    this.children = children;
 * };
 */

/**
 * @param {Node} root
 * @return {number[]}
 */
var postorder = function(root) {
  if (!root) return [];
  let res = [];
  function NPO(node) {
    if (!node) return;
    for (let c of node.children) {
      if (c) NPO(c);
    }
    res.push(node.val);
  }
  NPO(root);
  return res;
};

迭代

/**
 * // Definition for a Node.
 * function Node(val,children) {
 *    this.val = val;
 *    this.children = children;
 * };
 */

/**
 * @param {Node} root
 * @return {number[]}
 */
var postorder = function(root) {
  if (!root) return [];
  let res = [];
  let s = [root];
  let pre = null;
  while (s.length) {
    let node = s[s.length - 1];
    // 当前节点是叶节点或者当前节点的子节点已经被访问过就访问该节点
    if (!node.children.length || (pre && node.children.indexOf(pre) > -1)) {
      res.push(node.val);
      s.pop();
      pre = node;
    } else {
      for (let i = node.children.length - 1; i >= 0; i--) {
        let c = node.children[i];
        if (c) s.push(c);
      }
    }
  }
  return res;
};