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);
if(left && right) return root;
return left? left : right;
}
My C++ solution, easy understand


@Isabella_s : Yes, you are right. This problem's ideal time complexity of BST will be O(lgn). My solution's time complexity is O(n), so it is more suitable for the general tree.

class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { stack<TreeNode*> s1; stack<TreeNode*> s2; TreeNode* ptr=root; while(ptr!=NULL) { if(p>val>ptr>val) { s1.push(ptr); ptr=ptr>right; }else if(p>val<ptr>val) { s1.push(ptr); ptr=ptr>left; }else{ s1.push(ptr); break; }; }; ptr=root; while(ptr!=NULL) { if(q>val>ptr>val) { s2.push(ptr); ptr=ptr>right; }else if(q>val<ptr>val) { s2.push(ptr); ptr=ptr>left; }else{ s2.push(ptr); break; }; }; while(s1.size()>s2.size()) { s1.pop(); }; while(s1.size()<s2.size()) { s2.pop(); }; while(s1.top()!=s2.top()) { s1.pop(); s2.pop(); }; return s1.top(); } };