cpp 解法, 执行用时: 100 ms, 内存消耗: 249.8 MB, 提交时间: 2023-10-16 21:52:06

/*
// 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) {
        //////// 看一个Node有没有父亲
        unordered_set<Node *> has_parent;
        for (auto x: tree)
            for (auto y: x->children)
                has_parent.insert(y);
        for (auto x: tree)
            if (has_parent.find(x) == has_parent.end())
                return x;
        
        return NULL;    //仅仅为了编译通过
    }
    
    Node* findRoot2(vector<Node*> tree) {
        //////// 看一个Node有没有入
        unordered_set<Node *> has_in;
        for (auto x: tree)
            for (auto y: x->children)
                has_in.insert(y);
        for (auto x: tree)
            if (has_in.find(x) == has_in.end())
                return x;
        
        return NULL;    //仅仅为了编译通过
    }
};

java 解法, 执行用时: 15 ms, 内存消耗: 47.8 MB, 提交时间: 2023-10-16 21:51:09

/*
// 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) {
        HashSet<Node> set = new HashSet<Node>();
        for (Node node : tree) {
            for (Node child : node.children) {
                set.add(child);
            }
        }
        for (Node node : tree) {
            if (!set.contains(node)) {
                return node;
            }
        }
        return null;
    }
}

python3 解法, 执行用时: 120 ms, 内存消耗: 26.6 MB, 提交时间: 2023-10-16 21:50:37

"""
# 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':
        #### 看有没有父亲
        has_parent = set()
        for x in tree:
            for y in x.children:
                has_parent.add(y)
        for x in tree:
            if x not in has_parent:
                return x
                
    def findRoot2(self, tree: List['Node']) -> 'Node':
        #### 看有没有入
        has_in = set()
        for x in tree:
            for y in x.children:
                has_in.add(y)
        for x in tree:
            if x not in has_in:
                return x
                
    def findRoot3(self, tree: List['Node']) -> 'Node':
        #### 异或
        xornum = 0
        for x in tree:
            xornum ^= x.val
            for y in x.children:
                xornum ^= y.val

        for x in tree:
            if x.val == xornum:
                return x
                
    def findRoot4(self, tree: List['Node']) -> 'Node':
        node_depth = defaultdict(int)   #结点--深度

        #### 求结点的深度
        def get_depth(x : 'Node') -> int:
            if x in node_depth:
                return node_depth[x]
            if len(x.children) == 0:
                node_depth[x] = 1
                return 1
            max_dep = max([get_depth(y) for y in x.children])
            node_depth[x] = max_dep + 1
            return max_dep + 1

        for x in tree:
            get_depth(x)

        #### 最大深度
        max_dep = -1
        res = None
        for node, dep in node_depth.items():
            if dep > max_dep:
                max_dep = dep
                res = node
        return res

golang 解法, 执行用时: 12 ms, 内存消耗: 9.5 MB, 提交时间: 2023-10-16 21:49:11

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Children []*Node
 * }
 */
func findRoot(tree []*Node) *Node {
    a := 0
	for _, node := range tree {
		a ^= node.Val
		for _, child := range node.Children {
			a ^= child.Val
		}
	}
	for _, node := range tree {
		if node.Val == a {
			return node
		}
	}
	return nil
}

func findRoot1(tree []*Node) *Node {
	m := make(map[*Node]int)
	for _, node := range tree {
		if _, exist := m[node]; !exist {
			m[node] = 0
		}
		for _, child := range node.Children {
			m[child]++
		}
	}
	for node, times := range m {
		if times == 0 {
			return node
		}
	}
	return nil
}