LeetCode Entry

590. N-ary Tree Postorder Traversal

26.08.2024 easy 2024 kotlin

Postorder tree traversal

590. N-ary Tree Postorder Traversal easy blog post substack youtube 1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/714

Problem TLDR

Postorder tree traversal #easy #tree

Intuition

Visit children, then append current.

Approach

We can use the stack for iteration without recursion. Or we can use recursion with a separate collection to make it faster.

  • let’s just reuse the method’s signature neglecting the performance

Complexity

  • Time complexity: \(O(n^2)\)

  • Space complexity: \(O(n)\)

Code


    fun postorder(root: Node?): List<Int> = root?.run {
        children.map { postorder(it) }.flatten() + listOf(`val`)
    } ?: listOf()



    vector<int> postorder(Node* root) {
        vector<int> res;
        if (!root) return res;
        for (auto c : root->children)
            for (auto x : postorder(c))
                res.push_back(x);
        res.push_back(root->val);
        return res;
    }