经典算法实例应用：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 <= 104
• n 叉树的高度小于或等于 1000

解决方案

方法一：递归

思路

递归思路比较简单，N 叉树的前序遍历与二叉树的后序遍历的思路和方法基本一致，可以参考「145. 二叉树的后序遍历」的方法，每次递归时，先递归访问每个孩子节点，然后再访问根节点即可。

代码

Java

class Solution { public List<Integer> postorder(Node root) { List<Integer> res = new ArrayList<>(); helper(root, res); return res; } public void helper(Node root, List<Integer> res) { if (root == null) { return; } for (Node ch : root.children) { helper(ch, res); } res.add(root.val); } }

C++

class Solution { public: void helper(const Node* root, vector<int> & res) { if (root == nullptr) { return; } for (auto & ch : root->children) { helper(ch, res); } res.emplace_back(root->val); } vector<int> postorder(Node* root) { vector<int> res; helper(root, res); return res; } };

C#

public class Solution { public IList<int> Postorder(Node root) { IList<int> res = new List<int>(); Helper(root, res); return res; } public void Helper(Node root, IList<int> 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) 。