235.二叉搜索树的最近祖先
问题描述：
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）
个人分析：首先学到了它的性质来源百科：若它的左子树不空，则左子树上所有结点的值均小于它的 根结点 的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为 二叉排序树
对于结点root,p,q 大小关系存在三种（不妨令p<q）
1.root>q and root>p
2:root<q and root<p
3:p<root<q
先考虑3情况：思考这样一个问题 当满足3条件时 由小郑的笔记可知,root一定是p,q的祖先
那root一定是其最近祖先吗?
我们可用反证法解释：如果不是，那么假设最近祖先为root0，它必然不会出现在root的子树上（笔记上有说明，集合B，C中的元素有且仅有这一个公共祖先），那么它就只能出现在root以上，如果出现在root以上，深度就半小了，就不是最近祖先了，与题意要求不符。
所以如果出现了情况3 一定就是最近祖先的情况
所以情况3就是基线条件，情况1和2就是递归条件，下面呈现代码
class Solution: def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': # print(root) if p.left==q or p.right==q:#特殊情况 return p elif q.left==p or q.right==p:#特殊情况 return q elif q.val==root.val or p.val==root.val: return root else: if p.val<root.val<q.val or q.val<root.val<p.val : return root elif root.val>q.val or root.val>p.val : return self.lowestCommonAncestor(root.left,p,q) elif root.val<p.val or root.val<q.val: return self.lowestCommonAncestor(root.right,p,q) else: pass
