二叉树的最近公共祖先LCA

系列题目
236. 二叉树的最近公共祖先
1676. 二叉树的最近公共祖先IV
1644. 二叉树的最近公共祖先 II
235. 二叉搜索树的最近公共祖先
1650. 二叉树的最近公共祖先 III

class LowestCommonAncestor:"""236. 二叉树的最近公共祖先题目强调p和q一定存在于二叉树中，区别于1644题https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/"""def solution(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':def find(root, val1, val2):if not root:return None# 这里对应情况二if root.val == val1 or root.val == val2:return rootleft = find(root.left, val1, val2)right = find(root.right, val1, val2)# 这里对应情况一， 【后序位置，已经知道左右子树是否存在目标值】if left and right:# 当前节点是 LCA 节点return rootreturn left if left else rightreturn find(root, p.val, q.val)

class LowestCommonAncestor2:"""1676. 二叉树的最近公共祖先IV这道题把p和q换成了包含若干个节点的列表，同样这些列表里的所有节点一定存在于二叉树中，区别于1644题https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree-iv/"""def solution(self, root: 'TreeNode', nodes: List[TreeNode]) -> 'TreeNode':# 将列表转化成哈希集合，便于判断元素是否存在values = set()for node in nodes:values.add(node.value)self.find(root, values)def find(self, root: 'TreeNode', values):if not root:return None# 前序位置if root.value in values:return rootleft = self.find(root.left, values)right = self.find(root.right, values)# 后序位置，已经知道左右子树是否存在目标值if left and right:return rootreturn left if left else right

class LowestCommonAncestor3:"""1644. 二叉树的最近公共祖先 II输入一棵不含重复值的二叉树的，以及两个节点 p 和 q，这道题区别于236题，给定的两个节点p和q不一定存在于树中，不存在返回空指针，存在则返回最近公共祖先节点https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree-ii/"""def __init__(self):# 用于记录p和q是否存在于二叉树中self.foundP = Falseself.foundQ = Falsedef solution(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':res = self.find(root, p.val, q.val)if not self.foundP or not self.foundQ:return Nonereturn resdef find(self, root, val1, val2):"""在二叉树中寻找 val1 和 val2 的最近公共祖先节点:param root::param val1::param val2::return:"""if not root:return Noneleft = self.find(root.left, val1, val2)right = self.find(root.right, val1, val2)# 后续位置，判断当前节点是不是LCAif left and right:# 当前节点是 LCA 节点return root# 后续位置，判断当前节点是不是目标值if root.value == val1 or root.value == val2:if root.value == val1:self.foundP = Trueif root.value == val2:self.foundQ = Truereturn rootreturn left if left else right

class LowestCommonAncestor4:"""235. 二叉搜索树的最近公共祖先这是一颗BST树，要充分利用 左子节点 < 父节点 < 右子节点  的大小关系寻找LCAhttps://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/"""def solution(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':val1 = min(p.val, q.val)val2 = max(p.val, q.val)return self.find(root, val1, val2)# 在 BST 中寻找 val1 和 val2 的最近公共祖先节点def find(self, root, val1, val2):if not root:return Noneif root.val > val2:return self.find(root.left, val1, val2)elif root.val < val1:return self.find(root.right, val1, val2)else:  # val1 <= root.val <= val2return root

class LowestCommonAncestor5:"""1650. 二叉树的最近公共祖先 III这道题，给出的二叉树节点比较特殊，包括指向父节点的指针，和寻找两个单链表的相交的起始点做法一样【160. 相交链表】二叉树的最近公共祖先 IIIhttps://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree-iii/"""class Node:def __init__(self):self.val = Noneself.left = Noneself.right = Noneself.parent = Nonedef solution(self, p: 'Node', q: 'Node') -> 'Node':# 链表双指针技巧a, b = p, qwhile a != b:# a 走一步，如果走到根节点，转到 q 节点if not a:a = qelse:a = a.parent# b 走一步，如果走到根节点，转到 p 节点if not b:b = pelse:b = b.parentreturn a