一：解题思路
方法一：递归法，当p和q的值，都小于当前根节点上的值得时候，就递归到左子树上来。当p和q的值，都大于当前根节点上的值得时候，就递归到右子树上来。否者，如果不满足上述2种情况，这当前的根节点就是所求的节点。Time:O(h),Space:O(h)
方法二：迭代法。Time：O(h)，Space:O(1)
二：完整代码示例 (C++版和Java版)
递归C++:
class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if (p->val < root->val && q->val < root->val) { return lowestCommonAncestor(root->left,p,q); } else if(p->val>root->val && q->val>root->val) { return lowestCommonAncestor(root->right,p,q); } else { return root; } } };
递归Java：
class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if(p.val<root.val && q.val<root.val) return lowestCommonAncestor(root.left,p,q); else if(p.val>root.val && q.val>root.val) return lowestCommonAncestor(root.right,p,q); else return root; } }
迭代C++:
class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { while (root!=NULL) { if (p->val < root->val && q->val < root->val) { root = root->left; } else if (p->val > root->val && q->val > root->val) { root = root->right; } else { return root; } } return NULL; } };
迭代Java:
class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { while(root!=null) { if(p.val<root.val && q.val<root.val) root=root.left; else if(p.val>root.val && q.val>root.val) root=root.right; else return root; } return null; } }
p61 二叉搜索树的最近公共祖先 (leetcode 235)
原文：https://www.cnblogs.com/repinkply/p/12524143.html