leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0236.cpp (783B)

      1 class Solution {
      2   public:
      3     TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
      4         unordered_map<TreeNode *, TreeNode *> um;
      5         stack<TreeNode *> st;
      6         st.push(root);
      7         while (!st.empty()) {
      8             TreeNode *root = st.top();
      9             st.pop();
     10             if (root->left) {
     11                 um.insert({root->left, root});
     12                 st.push(root->left);
     13             }
     14             if (root->right) {
     15                 um.insert({root->right, root});
     16                 st.push(root->right);
     17             }
     18         }
     19 
     20         unordered_set<TreeNode *> ans;
     21         while (p) {
     22             ans.insert(p);
     23             p = um[p];
     24         }
     25 
     26         while (!ans.count(q)) {
     27             q = um[q];
     28         }
     29 
     30         return q;
     31     }
     32 };