经典算法实例应用：N叉树的后序遍历（一）

我们先来看题目描述:给定一个 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 104n 叉树的高度小于或等于 1000解决方案方法一递归思路递归思路比较简单N 叉树的前序遍历与二叉树的后序遍历的思路和方法基本一致可以参考「145. 二叉树的后序遍历」的方法每次递归时先递归访问每个孩子节点然后再访问根节点即可。代码Javaclass Solution { public ListInteger postorder(Node root) { ListInteger res new ArrayList(); helper(root, res); return res; } public void helper(Node root, ListInteger res) { if (root null) { return; } for (Node ch : root.children) { helper(ch, res); } res.add(root.val); } }Cclass Solution { public: void helper(const Node* root, vectorint res) { if (root nullptr) { return; } for (auto ch : root-children) { helper(ch, res); } res.emplace_back(root-val); } vectorint postorder(Node* root) { vectorint res; helper(root, res); return res; } };C#public class Solution { public IListint Postorder(Node root) { IListint res new Listint(); Helper(root, res); return res; } public void Helper(Node root, IListint res) { if (root null) { return; } foreach (Node ch in root.children) { Helper(ch, res); } res.Add(root.val); } }C#define MAX_NODE_SIZE 10000 void helper(const struct Node* root, int* res, int* pos) { if (NULL root) { return; } for (int i 0; i root-numChildren; i) { helper(root-children[i], res, pos); } res[(*pos)] root-val; } int* postorder(struct Node* root, int* returnSize) { int * res (int *)malloc(sizeof(int) * MAX_NODE_SIZE); int pos 0; helper(root, res, pos); *returnSize pos; return res; }复杂度分析时间复杂度O(m) 其中 m 为 N 叉树的节点。每个节点恰好被遍历一次。空间复杂度O(m) 递归过程中需要调用栈的开销平均情况下为 O(log m) 最坏情况下树的深度为 m−1需要的空间为 O(m−1) 因此空间复杂度为 O(m) 。