Leetcode Link: 236. 二叉树的最近公共祖先 - 力扣（LeetCode） (leetcode-cn.com) 剑指 Offer 68 - II. 二叉树的最近公共祖先 - 力扣（LeetCode）
题目
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
解法一
思路：DFS，自己思路，代码写出来有点low 明确一点，该代码需要得知左右子树里各自含有目标节点的个数，然后判断该节点是不是目标节点，三者一起考虑来确定该节点是不是公共的祖先节点
因为如果该节点为目标节点，而另一个目标节点是该节点的子孙节点，那么该节点就是公共祖先节点，因此在判断的时候需要先知道该节点是不是目标节点。
题解：
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
self.p = p
self.q = q
self.common_ancestor = None
# 这个flag用来指示已经找到了祖先节点
# 如果没有这个，那么假设p,q都在一个子树上，那么这个子树的父节点，爷爷节点会一直覆盖正确的值
self.find_flag = False
self.recur(root)
return self.common_ancestor
def recur(self, node):
if not node:
return 0
num_left = self.recur(node.left)
num_right = self.recur(node.right)
# 判断当前的节点是不是目标节点
if node == self.p or node == self.q:
nums = 1
else:
nums = 0
# 判断这个节点是不是公共的祖先节点
if (nums + num_left + num_right == 2) and (not self.find_flag):
self.find_flag = True
self.common_ancestor = node
# 返回当前子树中含有的目标节点的数量
return nums + num_left + num_right解法二
思路： 根据以上定义，若 root 是 p, q 的 最近公共祖先 ，则只可能为以下情况之一：
p 和 q 在 root 的子树中，且分列 root 的 异侧（即分别在左、右子树中）； p = root ，且 q 在 root 的左或右子树中； q = root ，且 p 在root 的左或右子树中；
考虑通过递归对二叉树进行先序遍历，当遇到节点 p 或 q 时返回。从底至顶回溯，当节点 p, q在节点 root 的异侧时，节点 root 即为最近公共祖先，则向上返回 root 。
递归解析：
- 终止条件： 当越过叶节点，则直接返回 null ； 当 root 等于 p,q ，则直接返回 root ；
- 递推工作： 开启递归左子节点，返回值记为 left ； 开启递归右子节点，返回值记为 right ； 返回值： 根据 left 和 right ，可展开为四种情况；
- 当 left 和 right 同时为空 ：说明 root 的左 / 右子树中都不包含 p,q ，返回 null ；
- 当 left 和 right 同时不为空 ：说明 p,q 分列在 root 的 异侧 （分别在 左 / 右子树），因此 root 为最近公共祖先，返回 root ；
- 当 left 为空 ，right 不为空 ：p,q 都不在 root 的左子树中，直接返回 right 。具体可分为两种情况：
- p,q 其中一个在 root 的 右子树 中，此时 right 指向 p（假设为 p ）；
- p,q 两节点都在 root 的 右子树 中，此时的 right 指向 最近公共祖先节点 ；
- 当 left 不为空 ， right 为空 ：与情况 3. 同理；
本思路通过返回值是不是None就直接相当于我的思路的
find_flag的作用。如果在同一个子树上，那就就会一直返回那个子树的头节点，也就是q, p的公共祖先节点。返回的过程中，另一边的子树返回的是None，就不会覆盖。
题解：
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if not root:
return None
# 碰到了就返回就行
if root == q or root == p:
return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
#1 左右都不为空，说明该节点为根节点
if (left!=None and right!=None): return root
#2 左右有一个为空，说明有一个在该子树上，另一个不在
if (left==None and right!=None): return right
if (left!=None and right==None): return left
#3 左右都为空，说明都不在子树上
if (left==None and right==None): return None