Leetcode Solutions Index

Thangaraj N — Tue, 20 Apr 2021 09:55:14 +0000

As I started to solve leetcode problems, wanted to document those somewhere where it might be useful for others as well. And so here you are at the main index page of my Leetcode solutions and explanations. I have organized the solutions based on their difficulty level and added a column to show which topics they can be related to. I hope these solutions will be useful for each one of you, if so, please like the posts which helped you.

Hard-Level Problems

#	Problem Title	Related Topics

Medium-Level Problems

#	Problem Title	Related Topics

Easy-Level Problems

#	Problem Title	Related Topics
589	N-ary Tree Preorder Traversal	Tree, DFS, Preorder

Cpp Solution: N-ary Tree Preorder Traversal (leetcode 589)

Thangaraj N — Tue, 20 Apr 2021 09:54:07 +0000

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

LeetCode Problem #589 Link

Problem:

Given the root of an n-ary tree, return the preorder traversal of its nodes' values.

N ary-Tree input serialization is represented in their level order traversal. Each group of children is separated by the null value (See examples)

Example 1
Input	root = [1,null,3,2,4,null,5,6]
Output	[1,3,5,6,2,4]
Visual

Example 2
Input	root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output	[1,2,3,6,7,11,14,4,8,12,5,9,13,10]
Visual

Constraints:

The number of nodes in the tree is in the range [0, 10^4].
0 <= Node.val <= 10^4
The height of the n-ary tree is less than or equal to 1000.

Idea/Approach:

Pre-order traversal is one type of Depth-First Search (DFS) algorithm. We can solve this problem by using the recursive DFS option. ( add the root(parent) to the result and call DFS recursively for each child)

C++ Solution:

class Solution {
public:
    vector<int> result;
    void preorderutil(Node * root) {
        result.push_back(root->val);
        int size = root->children.size();
        for(int i = 0; i< size; i++)
            preorderutil(root->children[i]);
    }
    vector<int> preorder(Node* root) {  
        if(!root)
            return {};
        preorderutil(root);
        return result;

    }
};

DEV Community: Thangaraj N