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

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

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) —

推荐阅读：
“位数”和“数位”的意义为什么不同？　 节约用水的资料　 求发芽率、合格率、出粉率等百分率的公式中为什么都要乘100%？　 为什么公历7月和8月都是31天　 引流粉丝到公众号，网站运营的一点思考，引流技巧实操　 站长如何赚钱？下面七条你做到了么？　 个人站长成功的七条经验分享　 个人站长必备的几个专业网站，能快速提高你的效率　 站长赚钱方法 联盟广告赚钱方法　 “时刻”和“时间”有什么不同？　
评论列表
添加评论