Given the root of a binary tree, the depth of each node is the shortest distance to the root.
Return the smallest subtree such that it contains all the deepest nodes in the original tree.
A node is called the deepest if it has the largest depth possible among any node in the entire tree.
The subtree of a node is tree consisting of that node, plus the set of all descendants of that node.
 
Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4]
Output: [2,7,4]
Explanation: We return the node with value 2, colored in yellow in the diagram.
The nodes coloured in blue are the deepest nodes of the tree.
Notice that nodes 5, 3 and 2 contain the deepest nodes in the tree but node 2 is the smallest subtree among them, so we return it.

Example 2:
Input: root = [1]
Output: [1]
Explanation: The root is the deepest node in the tree.

Example 3:
Input: root = [0,1,3,null,2]
Output: [2]
Explanation: The deepest node in the tree is 2, the valid subtrees are the subtrees of nodes 2, 1 and 0 but the subtree of node 2 is the smallest.

 
Constraints:

The number of nodes in the tree will be in the range [1, 500].
The values of the nodes in the tree are unique.

Difficulty: interview

Starter code:

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right
class Solution:
    def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:
        

Solutions:
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:
        # solution with DFS
        def dfs(node, depth):
            if not node:
                return node, depth
            left, l_depth = dfs(node.left, depth + 1)
            right,r_depth = dfs(node.right,depth + 1)
            if l_depth > r_depth:
                return left, l_depth
            if r_depth > l_depth:
                return right,r_depth
            return node,l_depth
        return dfs(root,0)[0]

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:
        def helper(root):
            if not root:
                return None, 0
            left, h_l = helper(root.left)
            right, h_r = helper(root.right)
            if h_l == h_r:
                return root, h_l + 1
            return (left, h_l+1) if h_l > h_r else (right, h_r + 1)
        node, _ = helper(root)
        return node

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
import heapq

class Solution:
    def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:
        nodes = []
        self.counter = 0
        def dfs(root, nodes, depth):
            if not root.left and not root.right:
                heapq.heappush(nodes, (-depth, self.counter, root))
                self.counter += 1
            if root.left:
                dfs(root.left, nodes, depth + 1)
            if root.right:
                dfs(root.right, nodes, depth + 1)
        dfs(root, nodes, 0)
        deepestNodes = []
        foundArr = []
        maxDepth = nodes[0][0]
        while nodes and nodes[0][0] == maxDepth:
            deepestNodes.append(heapq.heappop(nodes)[2])
            foundArr.append(False)
        def helper(root, deepestNodes, foundArr):
            for i in range(len(deepestNodes)):
                if root == deepestNodes[i]:
                    foundArr[i] = True
                    break
            leftArr = foundArr[:]
            rightArr = foundArr[:]
            leftFound = False
            rightFound = False
            if root.left:
                resLeft = helper(root.left, deepestNodes, leftArr)
                leftFound = True
                for i in leftArr:
                    if not i:
                        leftFound = False
                        break
            if root.right and not leftFound:
                resRight = helper(root.right, deepestNodes, rightArr)
                rightFound = True
                for i in rightArr:
                    if not i:
                        rightFound = False
                        break
            found = True
            for i in range(len(foundArr)):
                foundArr[i] = foundArr[i] or leftArr[i] or rightArr[i]
            if leftFound:
                return resLeft
            elif rightFound:
                return resRight
            for i in foundArr:
                if not i:
                    found = False
                    break
            if found:
                return root
            else:
                return None
        return helper(root, deepestNodes, foundArr)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:
        
        
        def getDepth(root):
            if not root:
                return 0
            left=getDepth(root.left)
            right=getDepth(root.right)
            return 1+max(left,right)
        
        def getSubtrees(root):
            if root:
                
                leftDepth=getDepth(root.left)
                rightDepth=getDepth(root.right)
                if leftDepth==rightDepth:
                    return root
                elif leftDepth>rightDepth:
                    return getSubtrees(root.left)
                else:
                    return getSubtrees(root.right)
                
        return getSubtrees(root)


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
import heapq

class Solution:
    def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:
        nodes = []
        self.counter = 0
        
        def dfs(root, nodes, depth):
            if not root.left and not root.right:
                heapq.heappush(nodes, (-depth, self.counter, root))
                self.counter += 1
            if root.left:
                dfs(root.left, nodes, depth + 1)
            if root.right:
                dfs(root.right, nodes, depth + 1)
        dfs(root, nodes, 0)
        deepestNodes = []
        foundArr = []
        maxDepth = nodes[0][0]
        while nodes and nodes[0][0] == maxDepth:
            deepestNodes.append(heapq.heappop(nodes)[2])
            foundArr.append(False)
            
        def helper(root, deepestNodes, foundArr):
            for i in range(len(deepestNodes)):
                if root == deepestNodes[i]:
                    foundArr[i] = True
                    break
            leftArr = foundArr[:]
            rightArr = foundArr[:]
            leftFound = False
            rightFound = False
            if root.left:
                resLeft = helper(root.left, deepestNodes, leftArr)
                leftFound = True
                for i in leftArr:
                    if not i:
                        leftFound = False
                        break
            if root.right and not leftFound:
                resRight = helper(root.right, deepestNodes, rightArr)
                rightFound = True
                for i in rightArr:
                    if not i:
                        rightFound = False
                        break
            found = True
            for i in range(len(foundArr)):
                foundArr[i] = foundArr[i] or leftArr[i] or rightArr[i]
            if leftFound:
                return resLeft
            elif rightFound:
                return resRight
            for i in foundArr:
                if not i:
                    found = False
                    break
            if found:
                return root
            else:
                return None
            
        return helper(root, deepestNodes, foundArr)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:
        if not root:
            return root
        
        deepest = [[]]
        max_depth = [0]
        self.mark_depth_and_parent(root, deepest, max_depth)
        # print(f\"DEEPEST : {[n.val for n in deepest[0]]} @ DEPTH = {max_depth[0]}\")
        return self.get_lca(deepest[0])
        
    
    def mark_depth_and_parent(self, root, deepest, max_depth, depth=0, parent=None):
        if not root:
            return
        
        # print(f\"{root.val} | Depth : {depth}\")
        if depth > max_depth[0]:
            max_depth[0] = depth
            deepest[0] = [root]
        elif depth == max_depth[0]:
            deepest[0].append(root)
            
        root.depth = depth
        root.parent = parent
        self.mark_depth_and_parent(root.left, deepest, max_depth, depth + 1, root)
        self.mark_depth_and_parent(root.right, deepest, max_depth, depth + 1, root)
        
    def get_lca(self, deepest):
        while len(deepest) > 1:
            n1, n2 = deepest.pop(), deepest.pop()
            while n1 and n1.depth > n2.depth:
                n1 = n1.parent
            while n2 and n2.depth > n1.depth:
                n2 = n2.parent
            while n1 != n2:
                n1 = n1.parent
                n2 = n2.parent
            deepest.append(n1)
        return deepest[0]



# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:
        def deep(node):
            if not node:
                return 0, None
            ld=deep(node.left)
            rd=deep(node.right)
            
            if ld[0]>rd[0]:
                return ld[0]+1, ld[1]
            elif rd[0]>ld[0]:
                return rd[0]+1, rd[1]
            else:
                return ld[0]+1, node
            
            
        return deep(root)[1]

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:
        
        def helper(node, depth):
            if not node:
                return depth, None
            
            ld, ln = helper(node.left, depth+1)
            rd, rn = helper(node.right, depth+1)
            
            if ld == rd:
                return ld, node
            
            if ld > rd:
                return ld, ln
            
            if ld < rd:
                return rd, rn
            
        
        depth, res = helper(root, 0)
        
        return res

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:
        #   找最深节点的公共父节点
        
        #   The values of the nodes in the tree are unique.
        
        #   第一次遍历，记录每个节点的深度。然后找到最深的节点
        #   如果只有一个，返回他自己。有多个的？
        
        #   第二次遍历，记录每个目标节点的路径(路径长度相同)。再从右边找最后一个相同的节点。
        
        def calcdeep(root, d, level):
            if level not in d:
                d[level] = []
            d[level].append(root)
            r1 = r2 = level
            if root.left  != None:
                r1 = calcdeep(root.left , d, level+1)
            if root.right != None:
                r2 = calcdeep(root.right, d, level+1)
            return max(r1,r2)
        
        d = dict()
        maxl = calcdeep(root, d, 0)
        if len(d[maxl]) == 1:
            return d[maxl][0]
        
        #   寻找公共父节点啦        
        def check2(root, ts, prefix, d):
            if root == None:
                return
            prefix.append(root)
            if root in ts:
                d[root.val] = copy.deepcopy(prefix)
            
            check2(root.left , ts, prefix, d)
            check2(root.right, ts, prefix, d)
            prefix.pop()
            
        targets = d[maxl]
        d = dict()
        prefix = []
        check2(root, targets, prefix, d)
        idx = maxl-1
        # print(d)
        while idx >= 0:
            # print(idx)
            vals = list(d.values())
            t = vals[0][idx]
            failed = False
            for val in list(d.values()):
                if val[idx].val != t.val:
                    failed = True
                    break
            if failed == False:
                return t
            idx -= 1
        return None