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

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

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

推荐阅读：
数学题:客车从甲地到乙地要6小时；货车从乙地到甲地要8小时　 数学题:一件商品按成本提高30%，换季又打八折　 数学题:前三轮的平均的平均分是94　 数学题:财务室会计结账时，发现账面上少了890.1元钱　 数学题:一个玻璃瓶内原有盐是水的1/11　 数学题:把圆柱平均分成若干份后拼成一个长方体　 奥数题:甲乙两地中间有一座山岭　 奥数题:一份工作按计划的时间算　 简便计算题：1997÷(1997+1997/1998)+(1/1999)　 数学题:在比例尺1：5000的图纸上　
评论列表
添加评论