236. Lowest Common Ancestor of a Binary Tree
递归寻找p或q，如果找到，层层向上返回，知道 root 左边和右边都不为NULL：if (left!=NULL && right!=NULL) return root;
时间复杂度 O(n)，空间复杂度 O(H)
class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if (root==NULL) return NULL; if (root==p || root==q) return root; TreeNode *left=lowestCommonAncestor(root->left,p,q); TreeNode *right=lowestCommonAncestor(root->right,p,q); if (left!=NULL && right!=NULL) return root; if (left!=NULL) return left; if (right!=NULL) return right; return NULL; } };
235. Lowest Common Ancestor of a Binary Search Tree
实际上比上面那题简单，因为LCA的大小一定是在 p 和 q 中间，只要不断缩小直到在两者之间就行了。
class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if (root->val>p->val && root->val>q->val) return lowestCommonAncestor(root->left,p,q); if (root->val<p->val && root->val<q->val) return lowestCommonAncestor(root->right,p,q); return root; } };
原文：https://www.cnblogs.com/hankunyan/p/9532704.html