1506. Find Root of N-Ary Tree

문제: leetcode.com/problems/find-root-of-n-ary-tree/

 

mock interview를 수행하다가 막혀서... 문제 자체를 제대로 이해못했다.

 

 조건이 findRoot는 A arbitrary order 속성을 가진 array에서 root를 찾는 문제이며 findRoot는 drive code다.

 즉, serialized input data -> a arbitrary order array -> find root -> make a serialized date by using a root node 이런 흐름이다.

 root는 parent가 없으므로 parent가 없는 Node를 arbitrary한 order를 가진 array에서 찾으면 된다.

 

 set이나 visited array를 두고 child만 체크하면 체크되지않은 노드가 루트가 된다.   follow up으로 parent 값을 전부 더하고 child값을 전부 빼주면 root의 값이 나오고 이를 linear search해서 Node pointer만 찾아줘서 return해주면 space complexity가 O(1)이 된다.

 

/*
// 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:
    Node* findRoot(vector<Node*> tree) {
        int root = 0;
        
        for(auto parent : tree){
            root += parent->val;
            for(auto child : parent->children){
                root -= child->val;
            }
        }
        
        Node* ret = NULL;
        
        for(auto node : tree){
            if(node->val == root){
                ret = node;
                break;
            }
        }
        return ret;
    }
};