题目描述
这是 LeetCode 上的 590. N 叉树的后序遍历 ，难度为 简单。
Tag : 「递归」、「迭代」、「非递归」、「DFS」、「BFS」
给定一个 nn 叉树的根节点 rootroot ，返回 其节点值的 后序遍历 。
nn 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 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,104] 内
- 0 <= Node.val <= 10^40<=Node.val<=104
- nn 叉树的高度小于或等于 10001000
进阶：递归法很简单，你可以使用迭代法完成此题吗?
递归
常规做法，不再赘述。
代码：
class Solution { List<Integer> ans = new ArrayList<>(); public List<Integer> postorder(Node root) { dfs(root); return ans; } void dfs(Node root) { if (root == null) return; for (Node node : root.children) dfs(node); ans.add(root.val); } } 复制代码
- 时间复杂度：O(n)O(n)
- 空间复杂度：忽略递归带来的额外空间开销，复杂度为 O(1)O(1)
非递归
针对本题，使用「栈」模拟递归过程。
迭代过程中记录 (cnt = 当前节点遍历过的子节点数量, node = 当前节点) 二元组，每次取出栈顶元素，如果当前节点已经遍历完所有的子节点（当前遍历过的子节点数量为 cnt = 子节点数量cnt=子节点数量），则将当前节点的值加入答案。
否则更新当前元素遍历过的子节点数量，并重新入队，即将 (cnt + 1, node)(cnt+1,node) 入队，以及将下一子节点 (0, node.children[cnt])(0,node.children[cnt]) 进行首次入队。
代码：
class Solution { public List<Integer> postorder(Node root) { List<Integer> ans = new ArrayList<>(); Deque<Object[]> d = new ArrayDeque<>(); d.addLast(new Object[]{0, root}); while (!d.isEmpty()) { Object[] poll = d.pollLast(); Integer cnt = (Integer)poll[0]; Node t = (Node)poll[1]; if (t == null) continue; if (cnt == t.children.size()) ans.add(t.val); if (cnt < t.children.size()) { d.addLast(new Object[]{cnt + 1, t}); d.addLast(new Object[]{0, t.children.get(cnt)}); } } return ans; } } 复制代码
- 时间复杂度：O(n)O(n)
- 空间复杂度：O(n)O(n)
通用「非递归」
另外一种「递归」转「迭代」的做法，是直接模拟系统执行「递归」的过程，这是一种更为通用的做法。
由于现代编译器已经做了很多关于递归的优化，现在这种技巧已经无须掌握。
在迭代过程中记录当前栈帧位置状态 loc，在每个状态流转节点做相应操作。
代码：
class Solution { public List<Integer> postorder(Node root) { List<Integer> ans = new ArrayList<>(); Deque<Object[]> d = new ArrayDeque<>(); d.addLast(new Object[]{0, root}); while (!d.isEmpty()) { Object[] poll = d.pollLast(); Integer loc = (Integer)poll[0]; Node t = (Node)poll[1]; if (t == null) continue; if (loc == 0) { d.addLast(new Object[]{1, t}); int n = t.children.size(); for (int i = n - 1; i >= 0; i--) d.addLast(new Object[]{0, t.children.get(i)}); } else if (loc == 1) { ans.add(t.val); } } return ans; } } 复制代码
- 时间复杂度：O(n)O(n)
- 空间复杂度：O(n)O(n)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.590 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
