思路：
由于是二叉搜索树，很快想到了如果root大小位于p，q之间，则root为结果，否则pq位于同侧
然后自然想到了递归
class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if((((p.val>=root.val)&&(root.val>=q.val)))||(((q.val>=root.val)&&(root.val>=p.val))))//pq位于两侧，直接返回root节点 等于情况 { return root; } if(p.val>root.val) {return lowestCommonAncestor(root.right,p,q);} if(p.val<root.val) {return lowestCommonAncestor(root.left,p,q);} return root; } }
但这个写得太复杂了，标准的这么写就行：
class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if(root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right, p, q); if(root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left, p, q); return root; } }
接着看到解答，其实还有一种迭代的解法。递归的解法空间复杂度为On，迭代就不需要。
class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { while(root != null) { if(root.val < p.val && root.val < q.val) // p,q 都在 root 的右子树中 root = root.right; // 遍历至右子节点 else if(root.val > p.val && root.val > q.val) // p,q 都在 root 的左子树中 root = root.left; // 遍历至左子节点 else break; } return root; } }
以后在分析复杂度上还是要好好看一看
原文：https://www.cnblogs.com/take-it-easy/p/14379201.html