// My Solution
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        unordered_map<TreeNode*, int> mid;
        int pos = 1;
        midder(mid, root, pos);
        int pos_p = mid[p];
        int pos_q = mid[q];
        TreeNode* curr = root;
        while ((pos_p-mid[curr])*(pos_q-mid[curr]) > 0) {
            if ((pos_p-mid[curr]) > 0) {
                curr = curr->right;
            } else {
                curr = curr->left;
            }
        }
        return curr;
    }
    
    void midder(unordered_map<TreeNode*, int>& mid, TreeNode* root, int& pos) {
        if (root == NULL) {
            return;
        }
        midder(mid, root->left, pos);
        mid[root] = pos++;
        midder(mid, root->right, pos);
    }
};

// Best Solution
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root || root == p || root == q) {
            return root;
        }
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p , q);
        if (left && right) {
            return root;
        }
        return (left == NULL)? right: left;
    }
};