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
进阶：递归法很简单，你可以使用迭代法完成此题吗?
代码结果
运行时间: 23 ms, 内存: 17.6 MB
/*
* 思路：
* 使用递归和Java Stream API进行后序遍历。
* 首先检查根节点是否为空，如果为空则返回空列表。
* 对于每个子节点，递归调用后序遍历函数，将结果添加到流中。
* 最后，将当前节点的值添加到结果列表中。
*/
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.Stream;
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int val) {
this.val = val;
}
public Node(int val, List<Node> children) {
this.val = val;
this.children = children;
}
}
public class Solution {
public List<Integer> postorder(Node root) {
if (root == null) return List.of();
return Stream.concat(
root.children.stream().flatMap(child -> postorder(child).stream()),
Stream.of(root.val)
).collect(Collectors.toList());
}
}解释
方法:
这个题解使用了递归的深度优先搜索（DFS）的思路来解决 N 叉树的后序遍历问题。具体来说，它定义了一个辅助函数 dfs，对当前节点的所有子节点递归调用 dfs，等子节点都处理完后，将当前节点的值加入到结果数组中。最后，在主函数中调用 dfs，并返回结果数组。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在递归函数`dfs`中，如果当前节点`node`为`null`，直接返回的处理是否会影响到后序遍历的完整性？
▷🦆
题解中提到，对于每个节点，需要遍历其所有的子节点。这种递归方式处理大量子节点或深层次递归时是否有性能风险？
▷🦆
后序遍历定义中，节点的处理顺序应为左-右-根。在N叉树的情况下，代码是如何确保这一顺序的？
▷相关问题
二叉树的后序遍历
给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
示例 1：
输入：root = [1,null,2,3] 输出：[3,2,1]
示例 2：
输入：root = [] 输出：[]
示例 3：
输入：root = [1] 输出：[1]
提示：
- 树中节点的数目在范围
[0, 100]内 -100 <= Node.val <= 100
进阶：递归算法很简单，你可以通过迭代算法完成吗？
N 叉树的层序遍历
给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。
树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。
示例 1：
输入：root = [1,null,3,2,4,null,5,6] 输出：[[1],[3,2,4],[5,6]]
示例 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] 输出：[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]
提示：
- 树的高度不会超过
1000 - 树的节点总数在
[0, 10^4]之间
N 叉树的前序遍历
给定一个 n 叉树的根节点 root ，返回 其节点值的 前序遍历 。
n 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。
示例 1：
输入：root = [1,null,3,2,4,null,5,6] 输出：[1,3,5,6,2,4]
示例 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] 输出：[1,2,3,6,7,11,14,4,8,12,5,9,13,10]
提示：
- 节点总数在范围
[0, 104]内 0 <= Node.val <= 104- n 叉树的高度小于或等于
1000
进阶：递归法很简单，你可以使用迭代法完成此题吗?