O(n) solution, no recursion, single traverse, pointer flagging instead of visited array. C++


#1
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

typedef TreeNode* TN;

int Solution::lca(TreeNode* A, int B, int C) {
    vector<TN> dfstack;
    
    unordered_set<TN> pathB;
    vector<TN> pathC;
    
    //dfs
    dfstack.push_back(A);
    while(!dfstack.empty()){
        auto curr = dfstack.back();
        if(curr == NULL) {
            dfstack.pop_back();
            continue;
        }
        
        if(curr->val == B) pathB.insert(dfstack.begin(), dfstack.end());
        if(curr->val == C) pathC.insert(pathC.begin(), dfstack.begin(), dfstack.end());
        
        if((((long)curr->left) & 1) == false) {//not visited left
            dfstack.push_back(curr->left);
            curr->left = (TN)((long)curr->left | 1);
        } else if((((long)curr->right) & 1) == false) {//not visited right
            dfstack.push_back(curr->right);
            curr->right = (TN)((long)curr->right | 1);
        } else {//visited both
            curr->left = (TN)((long)curr->left & ~1);
            curr->right = (TN)((long)curr->right & ~1);
            dfstack.pop_back();
        }
    }
    
    if(pathB.empty() || pathC.empty()) return -1;
    for(auto it = pathC.rbegin(); it!=pathC.rend(); ++it){
        if(pathB.find(*it)!=pathB.end()){
            return (*it)->val;
        }
    }
}