Given all the nodes of an N-ary tree as an array Node[] tree where each node has a unique value. Find and return the root of the N-ary tree. Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).
Follow up: Can you find the root of the tree with O(1) additional memory space?
Notes:
The following input is only given to testing purposes.
You will receive as input a list of all nodes of the n-ary tree in any order.Example 1:
Input: [1,null,3,2,4,null,5,6]
Output: [1,null,3,2,4,null,5,6]Example 2:
Input: [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,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]Constraints:
The total number of nodes is between [1, 5*10^4].
Each node has a unique value.Hints:
Node with indegree 0 is the root
Using Hash Set to Find the Root of N-ary tree
We can add all the nodes into a hash set. Then we can remove children nodes from the set. The last (and only) node left in the set will be the root.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | /* // 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) { unordered_set<Node*> nodes; for (const auto &n: tree) { nodes.insert(n); } for (const auto &n: tree) { for (const auto &c: n->children) { nodes.erase(c); } } return *begin(nodes); } }; |
/* // 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) { unordered_set<Node*> nodes; for (const auto &n: tree) { nodes.insert(n); } for (const auto &n: tree) { for (const auto &c: n->children) { nodes.erase(c); } } return *begin(nodes); } };
O(N) running time (two passes), and O(N) space. We can slightly improve (early exit) by swapping the two loops: first add all the children nodes into the set, then we can go through the tree nodes to see which one does not appear in the set – that must be a root node.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | /* // 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) { unordered_set<Node*> nodes; for (const auto &n: tree) { for (const auto &c: n->children) { nodes.insert(c); } } for (const auto &n: tree) { if (!nodes.count(n)) { return n; } } return nullptr; } }; |
/* // 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) { unordered_set<Node*> nodes; for (const auto &n: tree) { for (const auto &c: n->children) { nodes.insert(c); } } for (const auto &n: tree) { if (!nodes.count(n)) { return n; } } return nullptr; } };
Using Math to Find the Root of the N-ary Tree with O(1) constant space
Given each node has a unique value/number, we can compute the sum of all nodes and sum of all children nodes. Thus the root must have a value which equals to the difference.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | /* // 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 sum = 0; int allChildren = 0; for (const auto &n: tree) { sum += n->val; for (const auto &c: n->children) { allChildren += c->val; } } for (const auto &n: tree) { if (n->val == sum - allChildren) { return n; } } return nullptr; } }; |
/* // 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 sum = 0; int allChildren = 0; for (const auto &n: tree) { sum += n->val; for (const auto &c: n->children) { allChildren += c->val; } } for (const auto &n: tree) { if (n->val == sum - allChildren) { return n; } } return nullptr; } };
O(1) constant space, and O(N) time. However this approach can not be generalized.
See also Python code for finding the root of the N-ary tree: Teaching Kids Programming – Find Root of N-Ary Tree using Hash Set
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: How Many Blocks and Total Rewards for a Steem Witness in the Past 24 Hours?
Next Post: Algorithm to Count the Number of Substrings With Only 1s