高端建设网站公司哪家好,企业网站的建立,wordpress图文直播插件,律师事务所网站建设方案系列题目 236. 二叉树的最近公共祖先 1676. 二叉树的最近公共祖先IV 1644. 二叉树的最近公共祖先 II 235. 二叉搜索树的最近公共祖先 1650. 二叉树的最近公共祖先 III class LowestCommonAncestor:236. 二叉树的最近公共祖先题目强调p和q一定存在于二叉树中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
