algoadvance

Leetcode 590. N

Problem Statement

You are given an n-ary tree represented as a Node which has a value and a list of child nodes. Perform a postorder traversal on the tree and return the list of values in postorder sequence.

Example:

Input:

         1
       / | \
     3   2  4
   / | 
  5  6

Output: [5, 6, 3, 2, 4, 1]

Node Definition

The Node structure is defined as:

class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

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

Clarifying Questions

  1. Are there any constraints on the size of the tree?
    • No specific constraints are given for this problem.
  2. Can the tree have a single node only?
    • Yes, the tree can have a single node. In this case, the postorder traversal would simply return the value of that single node.
  3. What should be returned for an empty tree?
    • An empty list should be returned for an empty tree.

Strategy

To perform the postorder traversal:

  1. Start from the root node.
  2. For each node, traverse all of its children recursively.
  3. Append the node’s value after all children have been visited.

We’ll use a recursive function for this solution as postorder traversal naturally fits a recursive approach.

  1. If the current node is null, return immediately as there’s nothing to process.
  2. Traverse all children by calling the postorder function on each child.
  3. After all children have been processed, add the current node’s value to the result list.

Code

Here’s the C++ implementation of the postorder traversal for an n-ary tree:

#include <vector>
using namespace std;

// 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:
    void postorderHelper(Node* root, vector<int>& result) {
        if (root == nullptr) {
            return;
        }
        
        for (Node* child : root->children) {
            postorderHelper(child, result);
        }
        
        result.push_back(root->val);
    }
    
    vector<int> postorder(Node* root) {
        vector<int> result;
        postorderHelper(root, result);
        return result;
    }
};

Time Complexity

The time complexity of this approach is O(n), where n is the number of nodes in the tree. This is because we visit each node exactly once.

The space complexity is also O(n) due to the recursive call stack and to store the resulting postorder traversal list.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI