How to Find Root of N-Ary Tree using the Hash Set?

  • 时间：2020-10-11 15:25:20
  • 分类：网络文摘
  • 阅读：88 次

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.

n-ary-tree How to Find Root of N-Ary Tree using the Hash Set? algorithms c / c++

n-ary-tree

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.

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读：
5 Easy Ways On How To Build An Authority Website　 How to Protect Your WordPress Site From Hackers　 Top 10 Relationship Blogs With the Best Pieces of Advice in 2020　 How to Construct Binary Search Tree from Preorder Traversal in P　 Dynamic Programming Algorithm to Compute the Block Sum in a Matr　 Smallest Multiple Algorithm using Bruteforce or GCD/LCM　 How many different ways can £2 be made using any number of coins　 Compute Factorial Digit Sum: Find the sum of the digits in the n　 Compute the Maximum Integer Right Triangles Solutions　 Power Digit Sum: What is the sum of the digits of the number 2^1　
评论列表
添加评论