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;
     }     
}