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

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

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

推荐阅读：
How to Check if Any Three Points can Make a Triangle?　 How to Convert Set to Vector in C++?　 Peeple App Embodies the Worst of Social Media　 10 Best Writing Quotes for Bloggers　 Will Dorsey be Twitter’s Next CEO?　 How to Use Email Etiquette in the Age of Email Overload　 Welcome to Twitter, Edward Snowden　 Goodbye, Book Clubs: Book Lovers Unite on Social Media　 Anonymous Attacks Saudi Government in Protest of Impending Execu　 Running a Chauvinistic Blog is a Bad Business Decision　
评论列表
添加评论