leetCode590。 N 叉树后序遍历

Question

我编写了考虑每个条件的代码。 我解决了测试用例，但我在测试用例 28 中遇到了错误，该错误太大了，所以我什至无法调试并遵循它。 所以我需要你的帮助。

1. 我的代码有什么问题？
2. 并给我一些关于编码风格和实践方式的建议。

下面是我的代码。

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

};
                

我的观点是在删除节点时，我删除哪个节点。 所以我使用布尔值 chk 制作了 while 循环。 现在我什至无法猜测问题是什么。

1. 帮我发现问题
2. 请善意地帮助我，并为我的编码风格和实践方式提供一些建议。 3.请告诉我解决问题的心态

Answer 1

所以我使用布尔值 chk 制作了 while 循环。

这个想法不错，但是你正在与

temp

进行比较，这是不可靠的，因为不能保证节点将具有所有不同的值。您应该比较节点 pointer 。

其次，你不需要循环。唯一可能出现匹配的情况是父节点的 last 子节点，因为该子节点是在其父节点之后立即被推入堆栈的。

我没有验证深层嵌套的代码，因为应该没有必要有这么多重复的代码。

以下是修复代码的方法：

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. 
                //    Travel upwards in tree:
                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;
    }
};