本题的思路是这样的： 因为二叉树难免要用到递归 本题要求“最近的公共祖先” 很明显，如果没有“最近”的限制，最上面的根节点就是公共祖先（因为pq均存在，所以它们一定位于最上面的根节点的左右子树中） 限制有了“最近”的限制 我们要先下沉到最底层 依次向上判断 如果底层（左右孩子）有非空的结果，就直接返回底层那个节点（即，如果低层的节点是公共祖先，那它一定是更近的公共祖先） 如果底层返回None，则当前层判断的标准是 1、这个节点是p，且它是q的祖先 2、这个节点是q，且它是p的祖先 3、这个节点是p的祖先，且是q的祖先 三个满足一条即可
这里 又涉及到一个新的判断，即node是p或q的祖先
其实实现也简单 我们设置两个全局变量的set()，分别从底层开始，储存二者的祖先 如果一个节点的左右孩子是p，或本身是p，则往p的set里加入这个节点 q一样
class Solution: def __init__(self): self.find = False self.p_anc = set() self.q_anc = set() def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': if root == None: return None x = self.lowestCommonAncestor(root.left,p,q) if x != None: return x y = self.lowestCommonAncestor(root.right,p,q) if y != None: return y if ((root==p) and self.isAncestor(root,q,'q')) or ((root==q) and self.isAncestor(root,p,'p')) or (self.isAncestor(root,p,'p') and self.isAncestor(root,q,'q')): return root else: return None def isAncestor(self,root,m,indicator): #indicator告知是往哪个set里记录 if root == None: return False select_set = self.p_anc if indicator == 'p' else self.q_anc if root in select_set: return True if root == m or self.isAncestor(root.left,m,indicator) or self.isAncestor(root.right,m,indicator): select_set.add(root) return True else: return False