递归法解N叉树的后序遍历

我们来看思路

递归思路比较简单，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 10000void 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;
}

JavaScript

var postorder = function(root) {const res = [];helper(root, res);return res;}const helper = (root, res) => {if (root == null) {return;}for (const ch of root.children) {helper(ch, res);}res.push(root.val);
};

Python3

class Solution:def postorder(self, root: 'Node') -> List[int]:ans = []def dfs(node: 'Node'):if node is None:returnfor ch in node.children:dfs(ch)ans.append(node.val)dfs(root)return ans

复杂度分析

• 时间复杂度：O(m) ，其中 m 为 N 叉树的节点。每个节点恰好被遍历一次。
• 空间复杂度：O(m) ，递归过程中需要调用栈的开销，平均情况下为 O(log m) ，最坏情况下树的深度为 m−1，需要的空间为 O(m−1) ，因此空间复杂度为 O(m) 。