Leetcode: N-ary Postorder Traversal

 This question is asked at Amazon, and it is relatively simply Leetcode Question. It is the N-ary post order traversal, and it goes as follows: 

Given the root of an n-ary tree, return postorder traversal of the node's values. We will traverse left, then traverse right, then visit the nodes. 

So we will visit at the end.   

 For this tree, we output A, C, E, D, B, H, I, G, F. So left, right, top. 

The algorithm is as follows: 

postorder(node)

    if node == null then return

    postorder(node.left)

    postorder(node.right)

    visit(node) 

We'll go through both the iterative an recursive states. 

Let's first go through the recursive first. 

class Solution {

    List<Integer> list = new ArrayList<Integer>();

    public List<Integer> postorder(Node root) {

        if(root == null) return list; 

        for(Node node: root.children) postorder(node);

        list.add(root.val);

        return list;

    }

}

and now, let's go through the other solution as well.

We're going to need a stack, and then get the list once we reach the end, then reverse the list. It's like depth first search where we pop the top and then go until there are no more children. 

class Solution {

    public List<Integer> postorder(Node root) {

        List<Integer> list = new ArrayList<>();

        if(root == null) return list;

        Stack<Node> stack = new Stack<>();

        stack.add(root); 

        while(!stack.isEmpty()) {

            root = stack.pop();

            list.add(root.val);

            for(Node node: root.children) stack.add(node);

        }

        Collections.reverse(list);    

        return list;

    }

}

Here's the C++ code: 

vector<int> postorder(Node* root) {

    if(root == NULL) return {};

    vector<int> res;

    stack<Node*> stk;

    stk.push(root); 

    while(!stk.empty()) {

        Node* temp = stk.top();

        stk.pop(); 

        for(int i = 0; i <temp->children.size(); i++) {

            stk.push(temp->children[i]);

        }

            res.push_back(temp->val);

    }

    reverse(res.begin(), res.end()); 

    return res;

}