package 二叉树.BT;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
/**
* https://leetcode-cn.com/problems/n-ary-tree-postorder-traversal/
* @author Huangyujun
*
*/
public class _590_N叉树的后序遍历 {
public class Node {
public int val;
public List<Node> children;
public Node() {
}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
}
//递归
List<Integer> list = new ArrayList<Integer>();
public List<Integer> postorder1(Node root) {
if(root == null) return list;
for(Node node: root.children) {
postorder(node);
}
//拿到当前结点
list.add(root.val);
return list;
}
//使用迭代
public List<Integer> postorder(Node root) {
LinkedList<Integer> res = new LinkedList<>();
if (root == null) {
return res;
}
Deque<Node> stack = new LinkedList<>();
stack.addLast(root);
while (!stack.isEmpty()) {
Node node = stack.poll();
//实现数据的倒序(改变先后顺序):不断的插入当前结点第一个位置
res.addFirst(node.val); //为啥要倒序:因为当前第一个元素插入的是根
//而后序是 孩子们 根
//且倒序:实现了 1 2 3 4 (addFirst)
for (Node item : node.children) {
stack.push(item); // 1 2 3 4 (头)
}
}
return res;
}
}