目录
1. 题目描述
给定一个 n 叉树的根节点 root ，返回 其节点值的 后序遍历 。
n 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。
示例 1：
输入：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]
?
提示：
节点总数在范围 [0, 10^4] 内
0 <= Node.val <= 10^4
n 叉树的高度小于或等于 1000
进阶：递归法很简单，你可以使用迭代法完成此题吗?
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/n-ary-tree-postorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题分析
2.1 递归
????????N叉树的后序遍历与二叉树的后序遍历基本相同。
? ? ? ? 是先遍历所有子树，最后遍历节点自身。参考Leetcode0145: 二叉树的后序遍历。
? ? ? ? 代码参见：postorderRecursion()
2.2 迭代
? ? ? ? 与二叉树遍历一样，也可以用迭代的方式来实现。
? ? ? ? 但是由于N叉树的N是不确定的（二叉树确定性地最多只有左子树和右子树），所以一方面需要使用for-loop循环处理来遍历children；另一方面，由于是for-loop内嵌于while循环之中，break/continue的控制需要注意，与二叉树时有差异。处理流程如下：
? ? ? ? (1)栈、visited、ans初始化
? ? ? ? (2)将根节点入栈，同时将根节点加入visited
? ? ? ? (3)当栈不为空：
? ? ? ? ? ? ? ? (3-1)从栈中弹出一个节点
? ? ? ? ? ? ? ? (3-2)遍历该节点的子节点，对于每个不在visited中的子节点：
? ? ? ? ? ? ? ? ? ? ? ? 如果该子节点为叶子节点，将其值加入ans以及visited，回到(3-2)
????????????????????????如果该子节点不是叶子节点，将该节点和该子节点入栈，回到(3)????????????????
? ? ? ? ? ? ? ? (3-4)如果该节点还有子节点待处理（即尚未加入ans）回到(3)
? ? ? ? ? ? ? ? (3-5)将其值加入ans，将其加入visited，回到(3)
? ? ? ? 以以上示例1为例，围绕进出栈的处理步骤如下所示：
? ? ? ? (1) 1入
? ? ? ? (2) 1出
? ? ? ? (3) 1入，3入
? ? ? ? (4) 3出，进ans/visited
? ? ? ? (5) 3入，5入
? ? ? ? (6) 5出，进ans/visited
? ? ? ? (7) 3出
? ? ? ? (8) 3入，6入
? ? ? ? (9) 6出，进ans/visited
? ? ? ? (10) 3出，进ans/visited
? ? ? ? (11) 1出
? ? ? ? (12) 1入，2入
????????(13) 2出，进ans/visited
? ? ? ? (14) 1出
? ? ? ? (15) 1入，4入
????????(16) 4出，进ans/visited
????????(17) 1出，进ans/visited
? ? ? ? 虽然略显繁琐，但是手动推演一遍，是确保完全理解的必经之路。
3. 代码实现
import time
from typing import List
from collections import deque
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
# def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
def postorderTraversalRecursion(self, root: TreeNode) -> List[int]:
if root==None:
return []
ans = []
if root.left != None:
left_lst = self.postorderTraversal(root.left)
ans = ans + left_lst
if root.right != None:
right_lst = self.postorderTraversal(root.right)
ans = ans + right_lst
ans.append(root.val)
return ans
def postorderTraversalIteration(self, root: TreeNode) -> List[int]:
if root==None:
return []
ans = []
s = deque() # Used as stack, instead of FIFO
visited = set()
s.append(root)
while len(s)>0:
hasChildrenNotYetProcessed = False
node = s.pop()
for child in node.children:
if (child not in visited):
s.append(node)
s.append(child)
hasChildrenNotYetProcessed = True
break
if hasChildrenNotYetProcessed:
continue
ans.append(node.val)
visited.add(node)
return ans 回到主目录：笨牛慢耕的Leetcode解题笔记(动态更新。。。)
https://chenxiaoyuan.blog.csdn.net/article/details/123040889