236. Lowest Common Ancestor of a Binary Tree

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == NULL) return NULL;
        else if (find(root->left, p) && find(root->left, q))
            return lowestCommonAncestor(root->left, p, q);
        else if (find(root->right, p) && find(root->right, q))
            return lowestCommonAncestor(root->right, p, q);
        else return root;
    }
private:
    bool find(TreeNode* node, TreeNode* search) {
        if (node == NULL) return false;
        else if (node == search) return true;
        else {
            return find(node->left, search) || find(node->right, search);
        }
    }
};

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root || root == p || root == q) return root;
    TreeNode* left = lowestCommonAncestor(root->left, p, q);
    TreeNode* right = lowestCommonAncestor(root->right, p, q);
	// 在左在右返回 root，在左返回左，在右返回右，都没有返回 NULL
    return !left ? right : !right ? left : root;
}