Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
class Solution {
public:
bool findPath(TreeNode* root, TreeNode* p, vector<TreeNode*> &path) {
if(!root) return false;
path.push_back(root);
if(root == p) return true;
if(findPath(root->left, p, path) || findPath(root->right, p, path)) return true;
path.pop_back();
return false;
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
vector<TreeNode*> a, b;
findPath(root, p, a);
findPath(root, q, b);
TreeNode *ans = nullptr;
for(int i = 0; i < a.size() && i < b.size() && a[i] == b[i]; i++) {
ans = a[i];
}
return ans;
}
};About Me
- Full Stack Web Developer
- Competitive Programmer