Easy
Related Topics: Stack / Tree / Depth-First Search
LeetCode Source

解題想法

後序尋訪在 N-ary 的 Tree

邏輯跟一般後續尋訪類似

只不過每一層時，要陸續使用每一層 N-ary 的節點進行下方步驟

先進行後續尋訪的遞迴，之後將當下的值儲存到 res

由於是後序尋訪，所以在最後要儲存 root 的值到 res

Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Python

class Solution:
    def postorder(self, root: 'Node') -> List[int]:
        self.res = []
        if root == None:
            return None
        self.post(root)
        self.res.append(root.val)
        return self.res

    def post(self, root):
        if root == None:
            return
        for i in root.children:
            self.post(i)
            self.res.append(i.val)

C++

class Solution {
public:
    vector<int> postorder(Node* root) {
        vector<int> res;
        if (root == nullptr)
            return res;
        post(root, res);
        res.push_back(root->val);
        return res;
    }

    void post(Node* root, vector<int>& res) {
        if (root == nullptr)
            return;
        for (auto child : root->children) {
            post(child, res);
            res.push_back(child->val);
        }
    }
};