iterative post order traversal of Nary tree

struct Node {

int val;   

vector<Node * > children;

}

솔루션 :

recursive 는 원래꺼랑 거의 같다.

class Node{

    ArrayList<Node> children;
    int val;
}

public static ArrayList<Node> getPostOrder(Node root){
    ArrayList<Node> results = new ArrayList<Node>();
    if(root == null){
        return results;
    }

    for(Node child : root.children){
        results.addAll(getPostOrder(child));
    }
    results.add(root);
    
    return results;
}

iterative는 스택을 사용하는 듯 이건 preorder인데 inorder이나 postorder은 parent node를 따로 parentstack 등에 담아서 보관했다가, 각 노드별 색깔 같은걸 칠해놓았다가 그 색을 전부 처리했으면 부모를 빼낸다 하는 식으로 작업해야 하겠다( 물론 하지는 않음 ^&^ )

class Node{
    ArrayList<Node> children;
    int val;
}

public static List<Node> get PostOrder(Node root){
    LinkedList<Node> results = new LinkedList<Node>();
    if(root == null){
        return results;
    }

    Stack<Node> unprocessed = new Stack<Node>();
    unprocessed.push(root);
    while(!unprocessed.isEmpty()){
        Node node = unprocessed.pop();
        results.addFirst(node);
        for(Node childNode : node.children){
            unprocessed.push(childNode);
        }
    }
    return results;
}

시간 복잡도 : O(N)

공간 복잡도 : O(N)