Skip to content

Instantly share code, notes, and snippets.

@shorttermmem
Created March 25, 2019 23:15
Show Gist options
  • Save shorttermmem/dc637c29a6461dbdbf9c913da903c604 to your computer and use it in GitHub Desktop.
Save shorttermmem/dc637c29a6461dbdbf9c913da903c604 to your computer and use it in GitHub Desktop.
LEETCODE 30
#include <stdio.h>
//**
// Definition for a binary tree node.
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
TreeNode* g_found = nullptr;
bool l,r = false;
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
isFound(root, p, q);
return g_found;
}
// DFS
void isFound(TreeNode* n, TreeNode* p, TreeNode* q)
{
if(n == nullptr ) return;
// LEFT
isFound(n->left, p, q);
// RIGHT
isFound(n->right, p, q);
if(n == p) l = true;
if(n == q) r = true;
else if(g_found) return;
// post tree walk
if(l && r)
g_found = n;
}
};
int main (void)
{
TreeNode a (1);
TreeNode b (2);
TreeNode c (3);
a.left = &b;
b.right = &c;
auto* node = Solution().lowestCommonAncestor(&a, &c, &a);
printf("%d", node->val);
return 0;
}
// (a, c)
// a l = true r = false
// |
// b l = true r = false
// |
// c l = true r = true
// g_found = c
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment