1
class Solution {
2
  public TreeNode subtreeWithAllDeepest(TreeNode root) {
3
    if (root.left == null && root.right == null) return root;
4
    int depth = findDepth(root);
5
    Queue<TreeNode> q = new LinkedList<>();
6
    q.offer(root);
7
    int count = 0;
8
    while (!q.isEmpty()) {
9
      int size = q.size();
10
      count++;
11
      if (count == depth) {
12
        break;
13
      }
14
      for (int i = 0; i < size; i++) {
15
        TreeNode cur = q.poll();
16
        if (cur.left != null) q.offer(cur.left);
17
        if (cur.right != null) q.offer(cur.right);
18
      }
19
    }
20
    Set<Integer> set = new HashSet<>();
21
    while (!q.isEmpty()) {
22
      set.add(q.poll().val);
23
    }
24
    return find(root, set);
25
  }
26

27
  public int findDepth(TreeNode root) {
28
    if (root == null) return 0;
29
    int left = findDepth(root.left);
30
    int right = findDepth(root.right);
31
    return 1 + Math.max(left, right);
32
  }
33

34
  public TreeNode find(TreeNode root, Set<Integer> set) {
35
    if (root == null) return root;
36
    if (set.contains(root.val)) return root;
37
    TreeNode left = find(root.left, set);
38
    TreeNode right = find(root.right, set);
39
    if (left != null && right != null) return root;
40
    else if (left != null) return left;
41
    else if (right != null) return right;
42
    else return null;
43
  }
44
}