Skip to content

Instantly share code, notes, and snippets.

@liuml07

liuml07/lca.cpp

Created December 4, 2013 06:55
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save liuml07/7783420 to your computer and use it in GitHub Desktop.
Save liuml07/7783420 to your computer and use it in GitHub Desktop.
Download ZIP
Find the lowest common ancestor of two tree nodes
Raw
lca.cpp
TreeNode *LCA(TreeNode *root, TreeNode *p, TreeNode *q) {
if (root == nulltpr || root == p || root == q)
return root;
else {
TreeNode *L = LCA(root->left, p, q);
TreeNode *R = LCA(root->right, p, q);
if (L && R)
return root;
else
return L ? L : R;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment