python-leetcode 48.二叉树的最近公共祖先
题目：
给定一个二叉树，找到该树中两个指定节点的最近公共祖先
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）
方法一：递归
遍历整棵二叉树，定义 fx 表示 x 节点的子树中是否包含 p 节点或 q 节点，如果包含为 true，否则为 false。那么符合条件的最近公共祖先 x 一定满足如下条件：
其中 lson 和 rson 分别代表 x 节点的左孩子和右孩子，flson && frson 说明左子树和右子树均包含 p 节点或 q 节点，如果左子树包含的是 p 节点，那么右子树只能包含 q 节点，反之亦然，因为 p 节点和 q 节点都是不同且唯一的节点，因此如果满足这个判断条件即可说明 x 就是我们要找的最近公共祖先。再来看第二条判断条件，这个判断条件即是考虑了 x 恰好是 p 节点或 q 节点且它的左子树或右子树有一个包含了另一个节点的情况，因此如果满足这个判断条件亦可说明 x 就是我们要找的最近公共祖先。
可能会疑惑这样找出来的公共祖先深度是否是最大的。其实是最大的，因为我们是自底向上从叶子节点开始更新的，所以在所有满足条件的公共祖先中一定是深度最大的祖先先被访问到，且由于 fx
本身的定义很巧妙，在找到最近公共祖先 x 以后，f x 按定义被设置为 true ，即假定了这个子树中只有一个 p 节点或 q 节点，因此其他公共祖先不会再被判断为符合条件。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
#用于寻找 p 和 q 的最近公共祖先
if (root is None or root==p or root==q):#已经递归到了叶子节点的None处,
return root
left=self.lowestCommonAncestor(root.left,p,q)#递归左子树，寻找p或q是否存在于左子树中
right=self.lowestCommonAncestor(root.right,p,q)#递归右子树寻找p或q是否存在于右子树中
if left and right: #如果 left 和 right 都不为空
return root #说明 p 和 q 分布在 root 的左右子树中,当前 root 就是最近公共祖先
if not left: #果 left 为空，说明 p 和 q 都不在左子树
return right #直接返回 right（即 p 或 q 存在的地方）
if not right: #如果 right 为空，说明 p 和 q 都不在右子树
return left #直接返回 left（即 p 或 q 存在的地方）
return None #果 p 和 q 都不存在于 root 的子树中，则才会返回 None时间复杂度：O(N) 是二叉树的节点数。二叉树的所有节点有且只会被访问一次
空间复杂度：O(N)N 是二叉树的节点数。递归调用的栈深度取决于二叉树的高度，二叉树最坏情况下为一条链，此时高度为 N
方法二：存储父节点
用哈希表存储所有节点的父节点，然后我们就可以利用节点的父节点信息从 p 结点开始不断往上跳，并记录已经访问过的节点，再从 q 节点开始不断往上跳，如果碰到已经访问过的节点，那么这个节点就是我们要找的最近公共祖先
算法
- 从根节点开始遍历整棵二叉树，用哈希表记录每个节点的父节点指针。
- 从
p节点开始不断往它的祖先移动，并用数据结构记录已经访问过的祖先节点。 - 同样，我们再从
q节点开始不断往它的祖先移动，如果有祖先已经被访问过，即意味着这是p和q的深度最深的公共祖先，即 LCA 节点。
class Solution:
def __init__(self):
self.parent={} #存储节点的父节点
self.visited=set() #记录访问过的节点
def dfs(self,root):
#递归建立 parent 记录每个节点的父节点
if root.left: #如果 root.left 存在
self.parent[root.left.val]=root #记录左子树父节点
self.dfs(root.left)#递归调用
if root.right:#右节点存在
self.parent[root.right.val]=root#记录右节点的父节点
self.dfs(root.right)
def lowestCommonAncestor(self,root,p,q):
self.dfs(root) # # 先遍历整棵树，记录所有节点的父节点
while p: #从 p 开始，沿着 父节点路径 向上遍历，记录所有祖
self.visited.add(p.val)#存入 visited 集合，表示该节点已访问
p=self.parent.get(p.val) #获取 p 的父节点
while q: #从 q 开始，沿着父节点路径向上遍历
if q.val in self.visited:#如果 q 出现在 visited 集合中，说明 q 是 p 的祖先
return q
q=self.parent.get(q.val)#如果 q 还未出现，则继续向上移动
return None 时间复杂度：O(N)N 是二叉树的节点数。二叉树的所有节点有且只会被访问一次，从 p 和 q 节点往上跳经过的祖先节点个数不会超过 N
空间复杂度：O(N)N 是二叉树的节点数。递归调用的栈深度取决于二叉树的高度，二叉树最坏情况下为一条链，此时高度为 N，因此空间复杂度为 O(N)，哈希表存储每个节点的父节点也需要 O(N) 的空间复杂度
源自力扣官方题解