leetCode590. N-ary Tree Postorder Traversal

Question

I am trying to solve LeetCode problem 590. N-ary Tree Postorder:

Given the root of an n-ary tree, return the postorder traversal of its nodes' values.

I made code considering each condition.

I solved some test cases, but I got an error in testcase 28 which is so big that I can't even debug and follow it.

So I need your help.

1. What is wrong in my code?
2. Do you have some advice for coding style and way of practice?

Below is my code:

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;       // 벡터노드가 자식 노드들을 배열로 가지고 있다.

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<int> postorder(Node* root) {
        // 이진트리가 아니다 
        // 후순위 탐색이다. 
        // 자식부터 탐색한다는 점에서 우선 dfs인듯하다 -> stack 활용 

        vector<Node*> stack;
        Node* current = root;
        vector<int> ans;

        if(!current){
            return ans;
        }


        stack.push_back(current);           // stack에 넣기

        while(!stack.empty()) {

            current = stack.back();

            if(!(current->children).empty()){           // 자식이 있는 경우
                int n = (current->children).size();
                for(int i = n-1; i>=0;i--){
                    stack.push_back((current->children)[i]);
                }
            }

            else{
                ans.push_back(current->val);           // 자식이 없는 경우 
                int temp = (stack.back())->val;
                stack.pop_back();
                bool chk = false;            

                if(!stack.empty()){

                    current = stack.back(); // 3이 걸림
                    vector<Node*> v = current->children;
                    int m = v.size();

                    for(int i = 0; i < m; i++){  // 이걸 반복해야할텐데 
                        if((v[i]->val) == temp){  
                            chk = true;
                        } 
                    }

                    while(chk&&!stack.empty()) {                     // 쭉 딸려 올라가도록 

                        ans.push_back(current->val);     
                        int temp = (stack.back())->val;
                        stack.pop_back();
                        chk = false;
                        
                        if(!stack.empty()){
                            current = stack.back(); // 3이 걸림
                            vector<Node*> v = current->children;
                            int m = v.size();

                            for(int i = 0; i < m; i++){ // 이걸 반복해야할텐데 
                                if((v[i] ->val) == temp){  
                                    chk = true;
                                } 
                            }
                        }
                    }
                    // 3에서 탈출 
                }
            }


        }

        return ans;
    }

};
                

The challenging issue I had was when removing nodes from the stack, when to do it.

So I made a while loop using the boolean chk.

And now I can't even guess what is the problem:

1. What is my mistake?
2. Any advice for my coding style and way of practice?

Answer 1

So I made while loop using boolean chk.

The idea is not bad, but you are comparing with temp, which is not reliable, as there is no guarantee that the nodes will have all distinct values. You should compare the node pointer instead.

Secondly, you don't need a loop. The only time you should potentially have a match, is with the last child of a parent node, since that child was pushed on the stack right after its parent.

I didn't verify the deeply nested code, as it should not be necessary to have so much repetition of code. This is the common advice given: Don't repeat yourself.

Here is how you could fix your code:

class Solution {
public:
    vector<int> postorder(Node* root) {
        vector<Node*> stack;
        Node* current = root;
        Node* last = nullptr;
        vector<int> ans;
        
        if (!current){
            return ans;
        }
        stack.push_back(current);
        while (!stack.empty()) {
            current = stack.back();
            int n = (current->children).size();
            for (int i = n - 1; i >= 0; i--) {
                stack.push_back((current->children)[i]);
            }
            while (stack.size() > 0) {
                current = stack.back();
                if ((current->children).size() > 0 && current->children.back() != last) {
                    break; // current node needs to be expanded
                }
                // All children of current node were visited. 
                //    Output the node's value, and remove it from the stack
                last = current; // Keep track of last processed node
                ans.push_back(last->val);
                stack.pop_back();
            }
            // If at this point the stack is not empty, then its top has a 
            //  node that still needs to be expanded,
            //   ... which will happen in the next iteration of the loop
        }
        return ans;
    }
};