难度: Easy
给定一个 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, 104] 内0 <= Node.val <= 1041000进阶：递归法很简单，你可以使用迭代法完成此题吗?
运行时间: 23 ms
内存: 17.6 MB
"""
# Definition for a Node.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children
"""
class Solution:
def postorder(self, root: 'Node') -> List[int]:
result = []
def dfs(node):
if not node:
return
for nxt in node.children:
dfs(nxt)
result.append(node.val)
dfs(root)
return result
这个题解使用了递归的深度优先搜索（DFS）的思路来解决 N 叉树的后序遍历问题。具体来说，它定义了一个辅助函数 dfs，对当前节点的所有子节点递归调用 dfs，等子节点都处理完后，将当前节点的值加入到结果数组中。最后，在主函数中调用 dfs，并返回结果数组。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def postorder(self, root: 'Node') -> List[int]:
result = []
def dfs(node):
if not node:
return
# 递归处理所有子节点
for child in node.children:
dfs(child)
# 后序遍历，在子节点都处理完后，将当前节点的值加入结果数组
result.append(node.val)
dfs(root)
return result
在递归函数`dfs`中，当遇到`null`节点时直接返回是一种常见的处理方式，这种处理不会影响到后序遍历的完整性。因为`null`节点表示树中没有元素，或者已经到达了叶子节点的子节点，这是树的自然边界。处理`null`节点的返回，确保了递归调用不会在空节点上执行无效操作，从而保持了算法的效率和安全性。
对于每个节点遍历所有子节点的递归方式确实存在性能风险，特别是在处理具有大量子节点或者深层次的树结构时。递归调用会增加调用栈的深度，当树的深度非常大时，可能导致栈溢出。此外，递归处理大量子节点会消耗大量的计算资源，影响算法的时间效率。在这种情况下，可以考虑使用迭代方法配合栈来实现后序遍历，以减少递归带来的开销。
在N叉树的后序遍历中，节点的处理顺序扩展为先处理所有子节点，然后处理根节点。题解中通过递归地先遍历所有子节点，然后再将当前节点的值加入到结果数组中，从而实现了这一处理顺序。在每个节点的递归调用中，首先遍历并递归处理该节点的所有子节点，确保子节点的值先于当前节点被加入结果数组。这样，无论是左子节点、右子节点，还是其他任何子节点，都会在当前节点之前处理，从而保证了后序遍历的顺序要求。