1
# Definition for a binary tree node.
2
# class TreeNode:
3
#     def __init__(self, val=0, left=None, right=None):
4
#         self.val = val
5
#         self.left = left
6
#         self.right = right
7
class Solution:
8
    def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:
9

10
        # find a set of deepest nodes first
11
        deepest_nodes = [0]
12
        self.find_deepest(root, 0, deepest_nodes)
13

14
        # extract the depth and also make a set out of the values
15
        targets = set(deepest_nodes[1:])
16

17
        # get the subtree
18
        return self.find_merge(root, targets)[0]
19

20
    def find_deepest(self, node, current_depth, deepest_nodes):
21

22
        # make a check
23
        if not node:
24
            return
25

26
        # make a check if we are a deep node
27
        if current_depth > deepest_nodes[0]:
28
            deepest_nodes.clear()
29
            deepest_nodes.append(current_depth)
30
            deepest_nodes.append(node.val)
31
        elif current_depth == deepest_nodes[0]:
32
            deepest_nodes.append(node.val)
33

34
        # go deeper
35
        self.find_deepest(node.left, current_depth + 1, deepest_nodes)
36
        self.find_deepest(node.right, current_depth + 1, deepest_nodes)
37

38
    def find_merge(self, node, targets):
39

40
        # make a check
41
        if not node:
42
            return None, set()
43

44
        # check whether we are a target
45
        found = set()
46
        if node.val in targets:
47
            found.add(node.val)
48

49
        # go deeper and get result nodes
50
        nleft, left = self.find_merge(node.left, targets)
51
        if nleft is not None:
52
            return nleft, set()
53
        nright, right = self.find_merge(node.right, targets)
54
        if nright is not None:
55
            return nright, set()
56

57
        # merge the found set
58
        found = found | left | right
59

60
        # check whether we found all
61
        if not (targets - found):
62
            return node, set()
63
        else:
64
            return None, found