path_p = 3 1 0
path_1 = 3 1 8


class Solution {
public:
void FindPathImpl(stack<TreeNode *> &history, TreeNode *root,
TreeNode *target, bool &over) {
if (over) {
return;
}
history.push(root);
if (root == nullptr) {
return;
}
if (root == target) {
over = true;
return;
}
FindPathImpl(history, root->left, target, over);
if (over) {
return;
} else {

history.pop();
}
FindPathImpl(history, root->right, target, over);
if (over) {
return;
} else {

history.pop();
}
}
deque<TreeNode *> FindPath(TreeNode *root, TreeNode *target) {
stack<TreeNode *> history;
bool found = false;
FindPathImpl(history, root, target, found);
// reverse
deque<TreeNode *> ret;
while (!history.empty()) {
auto top = history.top();
history.pop();
ret.push_back(top);
}
return ret;
}
TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
auto sp = this->FindPath(root, p);
auto sq = this->FindPath(root, q);
auto prev = sp.back();
while (!sp.empty() && !sq.empty()) {
if (sp.back() != sq.back()) {
return prev;
}
prev = sp.back();
sp.pop_back();
sq.pop_back();
}
return prev;
}
};


1. 要么左右枝各一个
2. 要么都在同一枝
  TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
// case 1: one in left, another in right
auto left = lowestCommonAncestor(root->left, p, q);
auto right = lowestCommonAncestor(root->right, p, q);
if (left && right) {
return root;
}
// case 2: both in the same side
auto side = left ? left : right;
return lowestCommonAncestor(side, p, q);
}


class Solution {
public:
TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
if (root == nullptr) {
return nullptr;
}
if (root == p || root == q) {
return root;
}
// case 1: one in left, another in right
auto left = lowestCommonAncestor(root->left, p, q);
auto right = lowestCommonAncestor(root->right, p, q);
if (left && right) {
return root;
}
// case 2: both in the same side
auto side = left ? left : right;
return lowestCommonAncestor(side, p, q);
}
};


  TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
if (root == nullptr || root == p || root == q) return root;
// case 1: one in left, another in right
auto left = lowestCommonAncestor(root->left, p, q);
auto right = lowestCommonAncestor(root->right, p, q);
if (left && right) return root;
// case 2: both in the same side
return lowestCommonAncestor(left ? left : right, p, q);
}
`