2024 January 27 Problems

[daryl...@gmail.com]

Feel free to work on any of the problems you want; we'll have people present their solutions at 11:30.

Please post your solutions to this thread so others can use this as a reference.

589N-ary Tree Preorder Traversal75.3%Easy

590N-ary Tree Postorder Traversal77.7%Easy

For extra challenge, solve the two traversal problems with an iterative instead of recursive solution.

1600Throne Inheritance64.6%Medium

I am sick today so I won't be able to make the meeting. If anyone wants to make another Zoom meeting and post it in the thread, feel free to go ahead.

[Vivek H]

*********************************************************************

1600Throne Inheritance64.6%Medium

**********************************************************************

class ThroneInheritance {

public:

    typedef struct node {

        string name;

        int death;

        vector<struct node*> children;

    } NODE;

    map<string, NODE*> status;

    NODE* root;

   

    NODE* createNode(string name) {

        NODE* node = new NODE();

        node->name = name;

        node->death = 0;

        node->children = vector<NODE*>{};

        return node;

    }

   

    ThroneInheritance(string kingName) {

        root = createNode(kingName);

        status[kingName] = root;

    }

   

   

    void birth(string parentName, string childName) {

        //get the node for the parentName

        NODE* node = status[parentName];

        cout << "parentName:" << node->name << endl;

        //creat a child;

        NODE* child = createNode(childName);

       

        status[childName] = child;

        node->children.push_back(child);

     

    }

   

    void death(string name) {

        //get the node name

        NODE* node = status[name];

        node->death = 1;

    }

   

    void dfs(NODE* node, vector<string>& curOrder) {

     

        if(node->death == 0)

            curOrder.push_back(node->name);

        for(int i=0; i<node->children.size(); i++) {

            dfs(node->children[i], curOrder);

        }

    }

    vector<string> getInheritanceOrder() {

        vector<string> curOrder;

        dfs(root, curOrder);

        return curOrder;

       

    }

};

/**

 * Your ThroneInheritance object will be instantiated and called as such:

 * ThroneInheritance* obj = new ThroneInheritance(kingName);

 * obj->birth(parentName,childName);

 * obj->death(name);

 * vector<string> param_3 = obj->getInheritanceOrder();

 */

--
whatspp group: http://whatsapp.techbayarea.us/
---
You received this message because you are subscribed to the Google Groups "leetcode-meetup" group.
To unsubscribe from this group and stop receiving emails from it, send an email to leetcode-meet...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/leetcode-meetup/33ac9cfc-600e-48ef-bda8-0c0cf9efe595n%40googlegroups.com.

[Andriy T]

Time O(N) Space O(N) to hold the result.

589N-ary Tree Preorder Traversal

class Solution {

    public List<Integer> preorder(Node root) {

        List<Integer> res = new ArrayList<>();

        return traverseHelper(root, res);

    }

    private List<Integer> traverseHelper(Node root, List<Integer> res){

        if (root == null) {

            return res;

        }

        res.add(root.val);

        for (Node child: root.children) {

            traverseHelper(child, res);

        }

        return res;

    }

}

[Flocela Maldonado]

589N-ary Tree Preorder Traversal75.3%Easy
Time: O(n), Memory O(n);
class Solution {
public:
    vector<int> preorder(Node* root) {
        vector<int> ans{};

        stack<Node*> s{};

        if (root != nullptr)
        {
            s.push(root);
        }
       

        while (!s.empty())
        {
            Node* cur = s.top();
            s.pop();

            for (auto it = cur->children.rbegin(); it != cur->children.rend(); ++it)
            {
                s.push(*it);
            }
            ans.push_back(cur->val);
        }

        return ans;

    }
};

[Flocela Maldonado]

590N-ary Tree Postorder Traversal77.7%Easy

Time O(n), Memory O(n)

class Solution {
public:

    void rec(Node* node, vector<int>& ans)
    {
        for(auto it = node->children.begin(); it != node->children.end(); ++it)
        {
            rec(*it, ans);
        }
        ans.push_back(node->val);
    }

    vector<int> postorder(Node* root) {
        vector<int> ans{};
        if (root != nullptr)
        {
            rec(root, ans);
        }
        return ans;
    }
};

[Carlos Green]

/**

* // Definition for a Node.

* function Node(val, children) {

* this.val = val;

* this.children = children;

* };

preorder: root, left, right

inorder: left, root, right

postorder: left, right, root

iterate through the tree and grab the root value

at each node, then move to the left until we hit null

after that we can move back up the tree and hit the rest of the nodes

on the right hand side

Time & Space O(n) n = number of nodes

*/

/**

* @param {Node|null} root

* @return {number[]}

*/

// RECURSIVE SOLUTION

var preorder = function(root) {

const result = []

const traverse = node => {

if (!node) return

result.push(node.val)

while(node.children.length > 0) {

traverse(node.children.shift())

}

}

traverse(root)

return result

};

// ITERATIVE SOLUTION

var preorder = function(root) {

const result = []

let stack = [root]

while(stack.length > 0) {

const node = stack.shift()

if (!node) {continue}

result.push(node.val)

stack = [...node.children, ...stack]

}

return result

}

[Carlos Green]

/**

* // Definition for a Node.

* function Node(val,children) {

* this.val = val;

* this.children = children;

* };

preorder: root, left, right

inorder: left, root, right

postorder: left, right, root

itarte through the tree and grab the root value last

at each node, then move to the left until we hit null

after that we can move back up the tree and hit the rest of the nodes

Time & Space O(n) n = number of nodes

*/

/**

* @param {Node|null} root

* @return {number[]}

*/

// RECURSIVE SOLUTION

var postorder = function(root) {

const result = []

const traverse = node => {

if (!node) return

while(node.children.length > 0) {

traverse(node.children.shift())

}

result.push(node.val)

}

traverse(root)

return result

};

// ITERATIVE SOLUTION

var postorder = function(root) {

const result = []

let stack = [root]

while(stack.length > 0) {

const node = stack.pop()

if (!node) {continue}

stack = [...stack, ...node.children]

result.unshift(node.val)

}

return result

}

[Andriy T]

590N-ary Tree Postorder Traversal77.7%

Time O(N) space O(N)

class Solution {

    public List<Integer> postorder(Node root) {

        List<Integer> res = new ArrayList();

        if (root == null) return res;

        return postOrderHelper(root, res);

    }

    private List<Integer> postOrderHelper(Node root, List<Integer> res) {

        for (Node child: root.children) {

            postOrderHelper(child, res);

        }

        res.add(root.val);

        return res;

    }

}

[Flocela Maldonado]

1600Throne Inheritance64.6%Medium

class Node {

public:

string val = "";

vector<unique_ptr<Node>> children;

Node() {}

Node(string _val) {

val = _val;

}

};

class ThroneInheritance {

public:

unique_ptr<Node> king;

unordered_set<string> deaths{};

unordered_map<string, Node*> people;

Node* getNode(string name)

{

Node* matchingNode = nullptr;

stack<Node*> s{};

s.push(king.get());

while (!s.empty())

{

Node* cur = s.top();

s.pop();

if (cur->val == name)

{

matchingNode = cur;

}

else

{

for (auto it = cur->children.begin(); it != cur->children.end(); ++it)

{

s.push((*it).get());

}

}

}

return matchingNode;

}

ThroneInheritance(string kingName) {

king = make_unique<Node>(kingName);

people.insert({kingName, king.get()});

}

void birth(string parentName, string childName) {

Node* parentNode = people.at(parentName);

parentNode->children.push_back(make_unique<Node>(childName));

Node* childNode = parentNode->children[parentNode->children.size()-1].get();

people.insert({childName, childNode});

}

void death(string name) {

deaths.insert(name);

}

vector<string> getInheritanceOrder() {

vector<string> ans{};

stack<Node*> s{};

s.push(king.get());

while (!s.empty())

{

Node* cur = s.top();

s.pop();

for (auto it = cur->children.rbegin(); it != cur->children.rend(); ++it)

{

s.push((*it).get());

}

if (deaths.find(cur->val) == deaths.end() )

{

ans.push_back(cur->val);

}

}

return ans;

}

};

[Carlos Green]

Here is a zoom link for the meeting
https://us05web.zoom.us/j/82135169277?pwd=nMSMnKlvFC2wT4qCHAH8mEicBMoftV.1

On Saturday, January 27, 2024 at 11:23:34 AM UTC-8 redro...@gmail.com wrote:

[Carlos Green]

Here is the new link
https://us05web.zoom.us/j/83090001241?pwd=fatL9w4wHTgyPLHVyMDwgrfbXEiyIh.1

[Jagrut]

589 N-ary Tree Preorder Traversal

function preorder (root) {
    const res = [];
    _pre(root, res);
    return res;
};

function _pre(node, res) {
    if (node !== null) {
        res.push(node.val);
        for (const child of node.children) {
            _pre(child, res);
        }
    }
}

590 N-ary Tree Postorder Traversal

function postorder (root) {
    const res = [];
    _post(root, res);
    return res;
};

function _post(node, res) {
    if (node !== null) {
        for (const child of node.children) {
            _post(child, res);
        }
        res.push(node.val);
    }
}

1600 Throne Inheritance

class ThroneInheritance {
    constructor(kingName) {
        this.map = new Map();
        this.map.set(kingName, []);
        this.dead = new Set();
        this.kingName = kingName;
    }

    birth (parentName, childName) {
        (this.map.get(parentName) || []).push(childName);
        if (!this.map.has(childName)) {
this.map.set(childName, []);
}
    };

    death (name) {
        this.dead.add(name);
    };


    getInheritanceOrder () {
        const res = [];
        this._getOrder(this.kingName, res);
        return res;
    };
   
    _getOrder(curr, res) {
        if (!this.dead.has(curr)) {
            res.push(curr);
        }
        for (const c of this.map.get(curr)) {
            this._getOrder(c, res);
        }
    }
}

On Saturday, January 27, 2024 at 9:08:24 AM UTC-8 daryl...@gmail.com wrote:

[vinay]

589N-ary Tree Preorder Traversal75.3%Easy

time complexity O(n)

space o(n)

Recursive:

class Solution {
    List<Integer> result = new ArrayList<>();

    public List<Integer> preorder(Node root) {

        traverse(root);
        return result;
    }

    public void traverse(Node root){
        if(root == null){
            return;
        }

        result.add(root.val);

        for(Node child : root.children){
            traverse(child);
        }
    }
}

Iterative:

class Solution {
    public List<Integer> preorder(Node root) {

        List<Integer> result = new ArrayList<>();

        if(root == null){
            return result;
        }

        Deque<Node> stack = new ArrayDeque<>();
        stack.push(root);

        while(!stack.isEmpty()){
            Node cur = stack.pop();
            result.add(cur.val);
            if(cur.children != null){
                for(int i = cur.children.size()-1; i >= 0; i--){
                    stack.push(cur.children.get(i));
                }
            }
        }
        return result;
    }
}




590N-ary Tree Postorder Traversal77.7%Easy

time complexity O(n)
space o(n)

Iterative:

class Solution {

    public List<Integer> postorder(Node root) {
        LinkedList<Integer> result = new LinkedList<>();

        if(root == null){
            return result;
        }

        Deque<Node> stack = new ArrayDeque<>();
        stack.push(root);

        while(!stack.isEmpty()){
            Node cur = stack.pop();
            result.addFirst(cur.val);
            if(cur.children != null){
                for(int i = 0; i < cur.children.size(); i++){
                    stack.push(cur.children.get(i));
                }
            }
        }
        return result;
    }
}

Recursive

class Solution {
       LinkedList<Integer> result = new LinkedList<>();

 
    public List<Integer> postorder(Node root) {

        traverse(root);
        return result;
    }

    public void traverse(Node root){
        if(root == null){
            return;
        }

        result.addFirst(root.val);

        int size = root.children.size();
        for(int i = size-1; i >=0; i--){
            traverse(root.children.get(i));
        }
    }
    
}

--

whatspp group: http://whatsapp.techbayarea.us/
---
You received this message because you are subscribed to the Google Groups "leetcode-meetup" group.
To unsubscribe from this group and stop receiving emails from it, send an email to leetcode-meet...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/leetcode-meetup/a73384b2-2bc5-4785-a451-892c991c5ca0n%40googlegroups.com.