# LeetCode Lowest Common Ancestor of a Binary Tree

LeetCode Lowest Common Ancestor of a Binary Tree

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

```        _______3______
/              \
___5__          ___1__
/      \        /      \
6      _2       0       8
/  \
7   4
```

For example, the lowest common ancestor (LCA) of nodes `5` and `1` is `3`. Another example is LCA of nodes `5` and `4` is `5`, since a node can be a descendant of itself according to the LCA definition.

```struct MyNode {
TreeNode* node;
int par;
MyNode(TreeNode* n_, int p_) :node(n_), par(p_) {};
};
```

```class Solution {
private:
struct MyNode {
TreeNode* node;
int par;
MyNode(TreeNode* n_, int p_) :node(n_), par(p_) {};
};
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
vector<MyNode> nodes;
int i = 0, j = 0;
queue<MyNode> tree;
tree.push({ root,-1 });
while (!tree.empty()) {
MyNode cur = tree.front();
tree.pop();
if (cur.node == NULL) continue;
if (cur.node == p)i = nodes.size();
if (cur.node == q)j = nodes.size();
tree.push({ cur.node->left,nodes.size() });
tree.push({ cur.node->right,nodes.size() });
nodes.push_back(cur);
}

if (i == j)return nodes[i].node;

unordered_set<int> path1;
while (i != -1) {
path1.insert(i);
i = nodes[i].par;
}

while (j != -1) {
if (path1.find(j) != path1.end()) {
return nodes[j].node;
}
j = nodes[j].par;
}
return NULL;
}
};
```

```class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == NULL || root == p || root == q)return root;
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if (left != NULL&&right != NULL)return root;
return left != NULL ? left : right;
}
};
```