//AC  12ms  return the LCA or the node itself;
struct TreeNode* lowestCommonAncestor( struct TreeNode* root, struct TreeNode *p, struct TreeNode* q )
{
if(!p) return q; //corner case to accelerate from 16ms to 12ms;
if(!q) return p;
//the essential part: 1. p or q is the ancestor;
//2. p or q are in different subtrees so the LCA will be in the higher level;
if(!root  root == p  root == q) return root;
struct TreeNode *left = lowestCommonAncestor(root>left, p, q);
struct TreeNode *right = lowestCommonAncestor(root>right, p, q);
if(left&&right) return root; //in different subtrees;
if(!left) return right; //in the same subtree;
if(!right) return left;
}
Recursive solution in C, accepted as best and wellcommented


Clean solution of C++ enclosed
class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if(!root  root==p  root==q) return root; TreeNode *l = lowestCommonAncestor(root>left, p, q), *r = lowestCommonAncestor(root>right, p, q); if(l && r) return root; return l? l:r; } };