leetcode讲解--590. N-ary Tree Postorder Traversal

题目Given an n-ary tree, return the postorder traversal of its nodes’ values.For example, given a 3-ary tree:Return its postorder traversal as: [5,6,3,2,4,1].Note:Recursive solution is trivial, could you do it iteratively?题目地址讲解这道题跟先序遍历差不多，调换一下添加结点的顺序而已。参考：leetcode讲解–589. N-ary Tree Preorder Traversal但这道题的迭代解法稍微有点麻烦，需要一个标记，初次访问一个结点的时候我们并不能立即将它的值加进结果里，而是要等它的所有孩子访问完毕再加。也就是说我们第一次访问它并不pop，第二次访问它才pop。Java代码递归解法：/// Definition for a Node.class Node { public int val; public List<Node> children; public Node() {} public Node(int _val,List<Node> _children) { val = _val; children = _children; }};/class Solution { private List<Integer> result = new ArrayList<>(); public List<Integer> postorder(Node root) { if(root==null){ return result; } for(Node node:root.children){ postorder(node); } result.add(root.val); return result; }}迭代解法：/// Definition for a Node.class Node { public int val; public List<Node> children; public Node() {} public Node(int _val,List<Node> _children) { val = _val; children = _children; }};/class Solution { private List<Integer> result = new ArrayList<>(); private Stack<Bundle> stack = new Stack<>(); private Stack<Bundle> stack_temp = new Stack(); public List<Integer> postorder(Node root) { if(root==null){ return result; } Bundle rootBundle = new Bundle(root); stack.push(rootBundle); while(!stack.empty()){ Bundle bundle = stack.peek(); if(bundle.flag){ result.add(stack.pop().node.val); continue; } for(Node node:bundle.node.children){ Bundle d = new Bundle(node); stack_temp.push(d); } while(!stack_temp.empty()){ stack.push(stack_temp.pop()); } bundle.flag = true; } return result; } class Bundle{ Node node; Boolean flag; public Bundle(Node node){ flag = false; this.node = node; } }}