solved 'Lowest Common Ancestor of a Binary Tree' on leetcode https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/

lca_compare_path.cc

/*
  Run time: 28 ms.
  Used two vectors to record the path (left or right) to p & q.
  So O(log n) space.
 */

class Solution {
public:
  TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
    this->p_ = p;
    this->q_ = q;
    this->path_p_.clear();
    this->path_q_.clear();

    findPath(root);

    TreeNode *lca = root;
    // The branching node is the LCA.
    for (int i = 0, len = min(path_p_.size(), path_q_.size()); i < len; ++i) {
      if (path_p_[i] != path_q_[i]) {
        break;
      }
      else if (path_p_[i] == 0) {
        lca = lca->left;
      } else {
        lca = lca->right;
      }
    }
    return lca;
  }

private:
  void findPath(TreeNode *subroot) {
    // Check whether current subroot is p or q.
    // If yes, unset them to 'freeze' the path vectors. 
    if (subroot == p_) {
      p_ = NULL;
    }
    if (subroot == q_) {
      q_ = NULL;
    }

    // Both paths are already recorded.
    if (!p_ && !q_) {
      return;
    }

    if (subroot->left) {
      guardedPushBack(p_, path_p_, 0);
      guardedPushBack(q_, path_q_, 0);
      findPath(subroot->left);
    }
    if (subroot->right) {
      guardedPushBack(p_, path_p_, 1);
      guardedPushBack(q_, path_q_, 1);
      findPath(subroot->right);
    }

    guardedPopBack(p_, path_p_);
    guardedPopBack(q_, path_q_);
  }

  static inline void guardedPushBack(TreeNode *node, vector<char> &path,
                                     int direction) {
    if (node)
      path.push_back(direction);
  }

  static inline void guardedPopBack(TreeNode *node, vector<char> &path) {
    if (node)
      path.pop_back();
  }

  TreeNode *p_, *q_;
  vector<char> path_p_, path_q_;
};

lca_one_pass.cc

/*
  Run time: 24 ms.
  O(1) space in one pass.
  
  1. If a node with left part having p and right part having q, we know 
   it's the LCA (in top-down manner).
  2. Otherwise we return either p or q or null in its descents, to
   'report back'.
 */

class Solution {
public:
  TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root) {
      return nullptr;
    }
    
    this->p_ = p;
    this->q_ = q;
    return find(root);
  }
private:
  TreeNode *find(TreeNode *subroot) {
    if (subroot == p_ || subroot == q_) {
      return subroot;
    }
    
    TreeNode *find_in_left = 
      subroot->left == nullptr ? nullptr : find(subroot->left);
    TreeNode *find_in_right = 
      subroot->right == nullptr ? nullptr : find(subroot->right);
    
    if (find_in_left && find_in_right) {
      // Current node is the LCA of p & q.
      return subroot;
    } else {
      // Otherwise return the none-null one of p & q,
      // if existing.
      return find_in_left == nullptr ? find_in_right : find_in_left;
    }
  }

  TreeNode *p_, *q_;
};

lca_record_prev.cc

/*
  Run time: 48 ms.
  Used a hashmap to record path info.
  Roughly O(n) space.
 */

class Solution {
public:
  TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    this->p_ = p;
    this->q_ = q;
    prev.clear();
    prev[root] = nullptr;
    recordPath(root);

    // Calculate depths of p & q.
    int p_depth = 0, q_depth = 0;
    TreeNode *p_iter = p, *q_iter = q;
    while (prev[p_iter]) {
      ++p_depth;
      p_iter = prev[p_iter];
    } 
    while (prev[q_iter]) {
      ++q_depth;
      q_iter = prev[q_iter];
    }

    // Align p & q to the same level.
    while (p_depth > q_depth) {
      --p_depth;
      p = prev[p];
    }
    while (q_depth > p_depth) {
      --q_depth;
      q = prev[q];
    }

    // Find their commom ancestor.
    while (p != q) {
      p = prev[p];
      q = prev[q];
    }
    return p;
  }

private:
  void recordPath(TreeNode *subroot) {
    if (subroot == p_) {
      p_ = nullptr;
    }
    if (subroot == q_) {
      q_ = nullptr;
    }
    // If paths to p & q are already recorded, 
    // safe to leave.
    if (!p_ && !q_) {
      return;
    }

    if (subroot->left) {
      prev[subroot->left] = subroot;
      recordPath(subroot->left);
    }
    if (subroot->right) {
      prev[subroot->right] = subroot;
      recordPath(subroot->right);
    }
  }

  TreeNode *p_, *q_;
  unordered_map<TreeNode*, TreeNode*> prev;
};