题目

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?

讲解

这道题跟先序遍历差不多，调换一下添加结点的顺序而已。参考：

但这道题的迭代解法稍微有点麻烦，需要一个标记，初次访问一个结点的时候我们并不能立即将它的值加进结果里，而是要等它的所有孩子访问完毕再加。也就是说我们第一次访问它并不pop，第二次访问它才pop。

Java代码

递归解法：

/*// Definition for a Node.class Node {    public int val;    public List
    
      children;    public Node() {}    public Node(int _val,List
     
       _children) {        val = _val;        children = _children;    }};*/class Solution {    private List
      
        result = new ArrayList<>();    public List
       
         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
    
      children;    public Node() {}    public Node(int _val,List
     
       _children) {        val = _val;        children = _children;    }};*/class Solution {    private List
      
        result = new ArrayList<>();    private Stack
       
         stack = new Stack<>();    private Stack
        
          stack_temp = new Stack();    public List
         
           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; } }}