LeetCode 1506. Find Root of N-Ary Tree（异或）

文章目录

• • 1. 题目
  • 2. 解题

1. 题目

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.

Follow up:

Could you solve this problem in constant space complexity with a linear time algorithm?

Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).

在这里插入图片描述

For example, the above tree is serialized as [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].

Custom testing: You should provide the serialization of the input tree. The Driver code then extracts the nodes from the tree and shuffles them. You shouldn’t care how the extracted nodes are shuffled. The driver code will provide you with an array of the extracted nodes in random order and you need to find the root of the tree out of these nodes.

Example 1:

在这里插入图片描述

Input: tree = [1,null,3,2,4,null,5,6] Output: [1,null,3,2,4,null,5,6] Explanation: The input tree is shown above. The driver code first extracts the nodes so we now have an array of all tree nodes [Node(1),Node(3),Node(2),Node(4),Node(5),Node(6)], then the array is randomly shuffled, thus the actual input is [Node(5),Node(4),Node(3),Node(6),Node(2),Node(1)]. The root of the tree is Node(1) and the output is the serialization of the node you return.

Example 2:

在这里插入图片描述

Input: tree = [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.

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/find-root-of-n-ary-tree 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

• 把每个节点及其直接连接的子节点的值进行异或，题目说值无重复
• 这样根节点只运算了1次，其余节点运算了2次（异或偶数次抵消了）
• 最后遍历所有的节点，找到 val 等于异或值的就是根节点

/*
// 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 XOR = 0;
        for(Node* root : tree) 
        {
            XOR ^= root->val;
            for(Node* child : root->children)
                XOR ^= child->val;
        }
        for(Node* root : tree)
        {
            if(XOR == root->val)
                return root;
        }
        return NULL;
    }
};

248 ms 252.6 MB