# My C++ solution using dfs

• To get the LCA(Lowest Common Ancestor) of TreeNode p and q, the algorithm works as following:

1. Use dfs to calculate the depth and parent for each TreeNode;

2. Suppose depth[p] > depth[q], then let d = depth[p]-depth[q], first move p upwards d times and then move both p and q upwards until p and q point to the same node, which is the LCA of p and q;

class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
unordered_map<TreeNode*, int> depth;
unordered_map<TreeNode*, TreeNode*> parent;
dfs(root, NULL, 0, depth, parent);
if (depth[p] < depth[q])
swap(p, q);
int d = depth[p]-depth[q];
for (int i=0; i<d; i++)
p = parent[p];
while (p != q) {
q = parent[q];
p = parent[p];
}
return p;
}
void dfs(TreeNode* node, TreeNode* p, int d,
unordered_map<TreeNode*, int>& depth,
unordered_map<TreeNode*, TreeNode*>& parent) {
if (!node) return;
depth[node] = d;
parent[node] = p;
dfs(node->left, node, d+1, depth, parent);
dfs(node->right, node, d+1, depth, parent);
}
};

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