1、直接用递归的方法
使用递归的方法，找出二叉树中两个节点的最近公共祖先，分析如下：
对于两个节点p和q的公共祖先r，他们要么在r的同一边，要么在这个节点的两边，因此，只要满足这两个条件即可，也就是说： 只要 f(r.child, p) and f(r.child,q) 成立，这个r就可能是它俩的祖先。换一个角度说，r有两条支线，现在不管p和 q在哪条支线，只要两条支线都为真(即包含目标节点)，并且有一个交集，那这个交集这就是公共祖先。 这样的话，我们只要通过 p 和 q 一路标记他们经过的路径，然后如果两个标记在某一个节点相遇了，那这样就可以找出最近公共祖先了。
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
# 如果已经访问到根节点都没找到相应的目标节点，那么说明这条线应该被被标记为None，这条线就停止计算
# 如果到某一个节点，刚好是目标节点，则返回目标节点(不为空)，向上返回，标记这条线为有效的
if root is None or root == p or root == q:
return root
# 上面一步是判断到达某一个节点是是否要停止该条路径向下的迭代，如果不停止的话，应该做的事就是，通过判断当前节点的两条子路径
# 的情况，也就是子路径里是否包含目标节点，来判断当前节点向上返回的状态，下面的left和right分别为左边和右边返回的子树
# 的状态，分别标记是否有效
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
# 如果这个时候左右子路径刚好包含所有的目标节点，那么就说明这个root节点就是要找的公共子节点，直接返回这个节点即可
if left and right:
return root
# 如果这个节点不是公共祖先，那么它就从两颗子树那继承状态，并返回给上一级
if left:
return left
else:
return right
2、官方还给出了一种解题思路，就是用哈希表实现，下面就是用hashmap实现的思路。
用存储父节点的方式实现两个节点的最近公共祖先的查找。这个方法很直观，首先通过遍历的方式存储每个节点的父节点。 然后通过遍历的方式获取其中一个节点的所有父节点。遍历另一个节点的所有父节点，直到找到两者的交集点，即为所求的公共祖先。
这个方法相对于上面那个直接迭代判断的方法，消耗的内存资源会多一点。
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> bool:
def dfs(root, parent):
if root.left:
parent[root.left.val] = root
dfs(root.left, parent)
if root.right:
parent[root.right.val] = root
dfs(root.right, parent)
# 通过递归的方式，获取节点间父子关系的map
parent = {}
dfs(root, parent)
parent[root.val] = None
# 通过遍历的方式，找出其中一个目标节点到根节点的路劲
visit_p = {}
while p:
visit_p[p] = True
p = parent[p.val]
while q:
if visit_p.get(q, False):
return q
q = parent[q.val]
