# My C++ Solution

• ``````typedef std::tuple<int, TreeNode*> EulerNode;

class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == NULL) {
return NULL;
}

std::vector<EulerNode> nodeArray;
int pIndex = -1;
int qIndex = -1;
this->eulerTourTree(root, p, q, 0, nodeArray, pIndex, qIndex);

if (nodeArray.empty()
|| pIndex == -1
|| qIndex == -1) {
return NULL;
}

TreeNode *ret = NULL;
int currentLowestLevel = INT_MAX;
int smallIndex = std::min(pIndex, qIndex);
int bigIndex = std::max(pIndex, qIndex);
for (int i = smallIndex; i <= bigIndex; ++i) {
EulerNode node = nodeArray[i];
if (std::get<0>(node) < currentLowestLevel) {
currentLowestLevel = std::get<0>(node);
ret = std::get<1>(node);
}
}

return ret;
}
private:
void eulerTourTree(TreeNode* root, TreeNode* p, TreeNode* q, int level,
std::vector<EulerNode> &result, int &pIndex, int &qIndex) {
if (root == NULL) {
return;
}

result.push_back(std::make_tuple(level, root));

if (root == p && pIndex == -1) {
pIndex = result.size() - 1;
}

if (root == q && qIndex == -1) {
qIndex = result.size() - 1;
}

if (root->left != NULL) {
this->eulerTourTree(root->left, p, q, level+1, result, pIndex, qIndex);
result.push_back(std::make_tuple(level, root));
}

if (root->right != NULL) {
this->eulerTourTree(root->right, p, q, level+1, result, pIndex, qIndex);
result.push_back(std::make_tuple(level, root));
}
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.