#include <string>
#include <vector>
#include <list>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
using namespace std;

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q);
    TreeNode *P, *Q, *LCA;
    int postorder(TreeNode *n);
};

/* This returns the pq bits of node n. */

int Solution::postorder(TreeNode *n)
{
  int anc;

  if (n == nullptr) return 0;
  anc = 0;

  if (n == P) anc |= 1;     // If the node is p or q, then set the proper bit.
  if (n == Q) anc |= 2;

  // Call postorder on the left child, and then OR in the bits.  If both are set, then
  // this is the lowest common ancestor -- return it.

  if (n->left != NULL) anc |= postorder(n->left);
  if (anc == 3 && LCA == NULL) {
    LCA = n;
    return 3;
  }

  // Call postorder on the right child, and do the same thing that you did with the left child.

  if (n->right != NULL) anc |= postorder(n->right);
  if (anc == 3 && LCA == NULL) {
    LCA = n;
    return 3;
  }

  return anc;
}

TreeNode* Solution::lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
{
  P = p;
  Q = q;
  LCA = NULL;
  postorder(root);
  return LCA;
}