leetcode

0 class Solution {

1 public:

2 TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {

3 unordered_map<TreeNode *, TreeNode *> um;

4 stack<TreeNode *> st;

5 st.push(root);

6 while (!st.empty()) {

7 TreeNode *root = st.top();

8 st.pop();

9 if (root->left) {

10 um.insert({root->left, root});

11 st.push(root->left);

12 }

13 if (root->right) {

14 um.insert({root->right, root});

15 st.push(root->right);

16 }

17 }

18

19 unordered_set<TreeNode *> ans;

20 while (p) {

21 ans.insert(p);

22 p = um[p];

23 }

24

25 while (!ans.count(q)) {

26 q = um[q];

27 }

28

29 return q;

30 }

31 };