236. Lowest Common Ancestor of a Binary Tree

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/ 

Solution: 

One of the classical questions (The first time to see this question backs to my undergraduate...). The lowest common ancestor (LCA) should have the following features: 

1): the LCA itself is one of the two target nodes; 

2): if 1) is not the case, then the two target nodes should locate at different sides (left and right) of LCA; 

3): if we find two target nodes at the same side (left or right), then it is one of the ancestors, but not the LCA. So we need go to lower level for continuing search.

Code:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root || root == p || root == q) return root;
        bool a = findN(root->left, p), b = findN(root->right, q);
        if(a&&b || (!a && !b)) return root;
        if(a&&!b) return lowestCommonAncestor(root->left, p, q);
        return lowestCommonAncestor(root->right, p, q);
    }
private:
    bool findN(TreeNode* r, TreeNode* t){
        if(!r) return false;
        if(r == t) return true;
        return findN(r->left, t) || findN(r->right, t);
    }
};