1
/**
2
 * Definition for a binary tree node.
3
 * struct TreeNode {
4
 *     int val;
5
 *     TreeNode *left;
6
 *     TreeNode *right;
7
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
10
 * right(right) {}
11
 * };
12
 */
13
class Solution {
14
 public:
15
  void help(TreeNode *root, TreeNode *par, map<TreeNode *, TreeNode *> &m) {
16
    if (root == NULL) return;
17
    m[root] = par;
18
    help(root->left, root, m);
19
    help(root->right, root, m);
20
  }
21
  TreeNode *subtreeWithAllDeepest(TreeNode *root) {
22
    TreeNode *r = root;
23
    map<TreeNode *, TreeNode *> m;
24
    help(r, NULL, m);
25
    queue<TreeNode *> q;
26
    vector<TreeNode *> ans;
27
    q.push(root);
28
    while (!q.empty()) {
29
      int s = q.size();
30
      vector<TreeNode *> a;
31
      for (int i = 0; i < s; i++) {
32
        TreeNode *bgn = q.front();
33
        q.pop();
34
        a.push_back(bgn);
35
        if (bgn->left != NULL) q.push(bgn->left);
36
        if (bgn->right != NULL) q.push(bgn->right);
37
      }
38
      ans = a;
39
    }
40
    if (ans.size() == 1) return ans[0];
41
    set<TreeNode *> s;
42
    while (s.size() != 1) {
43
      s.clear();
44
      for (int i = 0; i < ans.size(); i++) {
45
        ans[i] = m[ans[i]];
46
      }
47
      s.insert(ans.begin(), ans.end());
48
    }
49
    for (auto i : s) {
50
      return i;
51
    }
52
    return NULL;
53
  }
54
};