Skip to content

Latest commit

 

History

History
238 lines (180 loc) · 6.44 KB

README.md

File metadata and controls

238 lines (180 loc) · 6.44 KB
Raw

1506. 找到 N 叉树的根节点

English Version

题目描述

给定一棵 N 叉树 的所有节点在一个数组  Node[] tree 中，树中每个节点都有 唯一的值 。

找到并返回 N 叉树的 根节点 。

 

自定义测试：

N 叉树的输入序列为其层序遍历序列，每组子节点用 null 分隔（见示例）。

上图中的 N 叉树的序列化描述为 [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] 。

测试将以下列方式进行：

  • 输入数据的形式为树的序列化描述。
  • 驱动程序代码将根据序列化的输入数据构造树，并以任意顺序将每个 Node 对象放入一个数组中。
  • 驱动程序代码将把数组传递给 findRoot ，你所编写的函数应该在数组中查找并返回根 Node 对象。
  • 驱动程序代码将接受返回的 Node 对象并对其进行序列化。如果序列化的结果和输入数据 相同 ，则测试 通过 。

 

示例 1：

输入：tree = [1,null,3,2,4,null,5,6]
输出：[1,null,3,2,4,null,5,6]
解释：来自输入数据的树如上所示。
驱动程序代码创建树，并以任意顺序向 findRoot 提供 Node 对象。
例如，传递的数组可以是 [Node(5),Node(4),Node(3),Node(6),Node(2),Node(1)] 或 [Node(2),Node(6),Node(1),Node(3),Node(5),Node(4)] 。
findRoot 函数应该返回根 Node(1) ，驱动程序代码将序列化它并与输入数据进行比较。
输入数据和序列化的 Node(1) 相同，因此测试通过。

示例 2：

输入：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]
输出：[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]

 

提示：

  • 节点的总个数在 [1, 5*10^4] 之间。
  • 每个节点都有唯一的值。

 

进阶：

  • 你可以使用 O(1) 额外内存空间且 O(n) 时间复杂度的算法来找到该树的根节点吗？

解法

遍历 N 叉树 tree 的所有节点以及它们的子节点：

  • 对于非根节点，它会在 tree 列表中出现一次，并且在某个节点的 children 列表中出现一次，一共出现两次。
  • 对于根节点，它只会在 tree 列表中出现一次。

我们对遍历到的节点及子节点进行按位异或运算，由于一个数异或两次等于没有进行任何运算，因此最后运算的结果就是根节点的值。

由于树中节点值唯一，我们再遍历一遍 tree 列表找出该节点即可。

Python3

"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children if children is not None else []
"""

class Solution:
    def findRoot(self, tree: List['Node']) -> 'Node':
        xorsum = 0
        for node in tree:
            xorsum ^= node.val
            for child in node.children:
                xorsum ^= child.val

        for node in tree:
            if node.val == xorsum:
                return node

Java

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;


    public Node() {
        children = new ArrayList<Node>();
    }

    public Node(int _val) {
        val = _val;
        children = new ArrayList<Node>();
    }

    public Node(int _val,ArrayList<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
    public Node findRoot(List<Node> tree) {
        int xor = 0;
        for (Node node : tree) {
            xor ^= node.val;
            for (Node child : node.children) {
                xor ^= child.val;
            }
        }
        for (Node node :tree) {
            if (node.val == xor) {
                return node;
            }
        }
        return null;
    }
}

C++

/*
// 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 xorsum = 0;
        for (auto& node : tree) {
            xorsum ^= node->val;
            for (auto& child : node->children) {
                xorsum ^= child->val;
            }
        }
        for (auto& node : tree) {
            if (node->val == xorsum) {
                return node;
            }
        }
        return nullptr;
    }
};

Go

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Children []*Node
 * }
 */

func findRoot(tree []*Node) *Node {
	xorsum := 0
	for _, node := range tree {
		xorsum ^= node.Val
		for _, child := range node.Children {
			xorsum ^= child.Val
		}
	}
	for _, node := range tree {
		if node.Val == xorsum {
			return node
		}
	}
	return nil
}

...