讨论/《N 叉树》 - N 叉树的后序遍历/
《N 叉树》 - N 叉树的后序遍历
共 1 个回复

迭代法:

/*
// Definition for a Node.
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;
    }
};
*/

class Solution {
    public List<Integer> postorder(Node root) {
        List<Integer> res=new ArrayList<>();
        if(root==null)return res;
        //遍历栈
        Stack<Node> stackFir=new Stack<Node>();
        //结果栈
        Stack<Node> stackSec=new Stack<Node>();
        stackFir.push(root);
        while(!stackFir.empty()){
            Node node=stackFir.pop();
            //正序遍历后stackFir顺序反 stackSec顺序正
            for(int index=0;index<node.children.size();index++)
            {
                stackFir.push(node.children.get(index));
            }
            stackSec.push(node);
        }
        while(!stackSec.empty()){
            Node node=stackSec.pop();
            res.add(node.val);
        }
        return res;
    }
}