给定一个 N 叉树，返回其节点值的后序遍历。
例如，给定一个 3叉树 :
返回其后序遍历: [5,6,3,2,4,1].
说明: 递归法很简单，你可以使用迭代法完成此题吗?
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/n-ary-tree-postorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解：
思路一：
递归，先遍历头节点，然后循环依次递归遍历头节点的子节点。代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
ArrayList list = new ArrayList();
public List<Integer> postorder(Node root) {
if (root == null) return list;
Node node = root;
for (int i = 0; i < node.children.size(); i++) {
Node n = node.children.get(i);
postorder(n);
}
list.add(root.val);
return list;
}
|
思路二：
迭代， 跟二叉树的后序遍历迭代法，逻辑一致。
- 将root入栈
- 循环执行以下操纵，直到栈为空
- 如果栈顶元素是叶子节点，或者上一次访问的节点是当前节点的子节点时，则栈顶元素出栈访问
- 否则，将栈顶元素的children从大到小依次入栈。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
// 迭代
public List<Integer> postorder(Node root){
ArrayList list = new ArrayList();
if (root == null) return list;
Stack<Node> stack = new Stack<>();
stack.push(root);
Node pre = null;
while (!stack.isEmpty()){
Node node = stack.peek();
if (node.children.size() == 0 || node.children.contains(pre)){
// 如果是叶子节点 或者 上一次访问的节点是此节点的子节点时 出栈访问
list.add(node.val);
pre = node;
stack.pop();
}else {
for (int i = node.children.size() - 1; i >= 0; i--) {
stack.push(node.children.get(i));
}
}
}
return list;
}
|