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.

What is wrong in my code?
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:

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

What is this code supposed to do? Please include a description in the question. Users on this site should not need to visit external sites to find out what your question is about. On a related note, code is read by people from around the world, so comments are much more useful when they are in English. — n. m. could be an AI
– n. m. could be an AI, Commented Jan 26, 2024 at 12:36
Input is root node and we need to post-order-travel and return it as vector. Thanks for your advice :) — my_first_step
– my_first_step, Commented Jan 27, 2024 at 0:05
So what does this do? if((v[i]->val) == temp){ chk = true; } Postorder traversal doesn't need to look at values. — n. m. could be an AI
– n. m. could be an AI, Commented Jan 27, 2024 at 9:18
I got problem on test-case 28 and that is so big testcase. So I coulden't debug it one by one and find what's the problem. — my_first_step
– my_first_step, Commented Jan 29, 2024 at 7:01

trincot · Accepted Answer · 2024-01-27 12:00:28Z

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;
    }
};

Thanks. Through this exampe, now I understand more about the difference between inorder-traversal and postorder-traversal.

Collectives™ on Stack Overflow

leetCode590. N-ary Tree Postorder Traversal

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related