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

示例

示例 1：
image.png
输入：root = [1,null,3,2,4,null,5,6]
输出：[5,6,3,2,4,1]

示例 2：

输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：[2,6,14,11,7,3,12,8,4,13,9,10,5,1]

题解

建立一个栈，遍历 N 叉树，取出该节点的第一个子节点推入栈
stack = [①] res = []
stack = [①③] res = []
stack = [①③⑤] res =[]

等到节点⑤没有子节点，推出⑤，记录数据5，指针再指向推出的③
stack = [①] res = [5]

将③推入栈，继续遍历第一个字节点⑥推入栈
stack = [①③⑥] res =[5]

节点⑥没有子节点，记录数据6，指针再指向推出的③
stack = [①] res =[5,6]

节点③已经没有子节点，记录数据3，，指针再指向推出的①
stack = [] res =[5,6,3]

遍历节点①，推入①和它的第一个子节点②
stack = [①②] res =[5,6,3]

节点耳没有子节点，记录数据2，重复以上
stack = [] res =[5,6,3,2]

  1. /**
  2.  * // Definition for a Node.
  3.  * function Node(val,children) {
  4.  *    this.val = val;
  5.  *    this.children = children;
  6.  * };
  7.  */
  9. /**
  10.  * @param {Node|null} root
  11.  * @return {number[]}
  12.  */
  13. var postorder = function(root) {
  14.     if (!root) {
  15.         return []
  16.     }
  18.     const stack = []
  19.     let cur = root
  20.     const res = []
  22.     while(stack.length || cur) {
  23.         if (cur) {
  24.             stack.push(cur)
  25.             cur = (cur.children && cur.children.length > 0) ? cur.children.shift() : null
  26.         } else {
  27.             const node = stack.pop()
  28.             res.push(node.val)
  29.             cur = stack.pop()
  30.         }
  31.     }
  33.     return res
  34. };

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/n-ary-tree-postorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。