LEETCODE 30

tree_lca.cc

#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