域名到期换个公司做网站,WordPress访问ip记录,网站的管理和维护,2018做网站前景好么本文参考labuladong算法笔记[拓展#xff1a;最近公共祖先系列解题框架 | labuladong 的算法笔记] 0、引言
如果说笔试的时候经常遇到各种动归回溯这类稍有难度的题目#xff0c;那么面试会倾向于一些比较经典的问题#xff0c;难度不算大#xff0c;而且也比较实用。
本…本文参考labuladong算法笔记[拓展最近公共祖先系列解题框架 | labuladong 的算法笔记] 0、引言
如果说笔试的时候经常遇到各种动归回溯这类稍有难度的题目那么面试会倾向于一些比较经典的问题难度不算大而且也比较实用。
本文就用 Git 引出一个经典的算法问题最近公共祖先Lowest Common Ancestor简称 LCA。
git pull 这个命令我们经常会用它默认是使用 merge 方式将远端别人的修改拉到本地如果带上参数 git pull -r就会使用 rebase 的方式将远端修改拉到本地。
这二者最直观的区别就是merge 方式合并的分支会看到很多「分叉」而 rebase 方式合并的分支就是一条直线。但无论哪种方式如果存在冲突Git 都会检测出来并让你手动解决冲突。
那么问题来了Git 是如何检测两条分支是否存在冲突的呢
以 rebase 命令为例比如下图的情况我站在 dev 分支执行 git rebase master然后 dev 就会接到 master 分支之上 这个过程中Git 是这么做的
首先找到这两条分支的最近公共祖先 LCA然后从 master 节点开始重演 LCA 到 dev 几个 commit 的修改如果这些修改和 LCA 到 master 的 commit 有冲突就会提示你手动解决冲突最后的结果就是把 dev 的分支完全接到 master 上面。
那么Git 是如何找到两条不同分支的最近公共祖先的呢这就是一个经典的算法问题了下面我来由浅入深讲一讲。 1、寻找一个元素
先不管最近公共祖先问题我请你实现一个简单的算法
给你输入一棵没有重复元素的二叉树根节点 root 和一个目标值 val请你写一个函数寻找树中值为 val 的节点。
函数签名如下
def find(root: TreeNode, val: int) - TreeNode:
这个函数应该很容易实现对吧比如我这样写代码
# 定义在以 root 为根的二叉树中寻找值为 val 的节点
def find(root: TreeNode, val: int) - TreeNode:# base caseif not root:return None# 看看 root.val 是不是要找的if root.val val:return root# root 不是目标节点那就去左子树找left find(root.left, val)if left:return left# 左子树找不着那就去右子树找right find(root.right, val)if right:return right# 实在找不到了return None
这段代码应该不用我多解释了我下面基于这段代码做一些简单的改写请你分析一下我的改动会造成什么影响。
首先我修改一下 return 的位置
def find(root: TreeNode, val: int) - TreeNode:if not root:return None# 前序位置if root.val val:return root# root 不是目标节点去左右子树寻找left find(root.left, val)right find(root.right, val)# 看看哪边找到了return left if left else right
这段代码也可以达到目的但是实际运行的效率会低一些原因也很简单如果你能够在左子树找到目标节点还有没有必要去右子树找了没有必要。但这段代码还是会去右子树找一圈所以效率相对差一些。
更进一步我把对 root.val 的判断从前序位置移动到后序位置
def find(root: TreeNode, val: int) - TreeNode:if root is None:return None# 先去左右子树寻找left find(root.left, val)right find(root.right, val)# 后序位置看看 root 是不是目标节点if root.val val:return root# root 不是目标节点再去看看哪边的子树找到了return left if left is not None else right
这段代码相当于你先去左右子树找然后才检查 root依然可以到达目的但是效率会进一步下降。因为这种写法必然会遍历二叉树的每一个节点。
对于之前的解法你在前序位置就检查 root如果输入的二叉树根节点的值恰好就是目标值 val那么函数直接结束了其他的节点根本不用搜索。
但如果你在后序位置判断那么就算根节点就是目标节点你也要去左右子树遍历完所有节点才能判断出来。
最后我再改一下题目现在不让你找值为 val 的节点而是寻找值为 val1 或 val2 的节点函数签名如下
def find(root: TreeNode, val1: int, val2: int) - TreeNode:
这和我们第一次实现的 find 函数基本上是一样的而且你应该知道可以有多种写法我选择这样写代码
# 定义在以 root 为根的二叉树中寻找值为 val1 或 val2 的节点
def find(root, val1, val2):# base caseif root is None:return None# 前序位置看看 root 是不是目标值if root.val val1 or root.val val2:return root# 去左右子树寻找left find(root.left, val1, val2)right find(root.right, val1, val2)# 后序位置已经知道左右子树是否存在目标值return left if left is not None else right
为什么要写这样一个奇怪的 find 函数呢因为最近公共祖先系列问题的解法都是把这个函数作为框架的。 2、秒杀五道题目
236. 二叉树的最近公共祖先
给你输入一棵不含重复值的二叉树以及存在于树中的两个节点 p 和 q请你计算 p 和 q 的最近公共祖先节点。
比如输入这样一棵二叉树 如果 p 是节点 6q 是节点 7那么它俩的 LCA 就是节点 5 当然p 和 q 本身也可能是 LCA比如这种情况 q 本身就是 LCA 节点 两个节点的最近公共祖先其实就是这两个节点向根节点的「延长线」的交汇点那么对于任意一个节点它怎么才能知道自己是不是 p 和 q 的最近公共祖先
如果一个节点能够在它的左右子树中分别找到 p 和 q则该节点为 LCA 节点。
这就要用到之前实现的 find 函数了只需在后序位置添加一个判断逻辑即可改造成寻找最近公共祖先的解法代码
【python】
class Solution:def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) - TreeNode:return self.find(root, p.val, q.val)# 在二叉树中寻找 val1 和 val2 的最近公共祖先节点def find(self, root: TreeNode, val1: int, val2: int) - TreeNode:if not root:return None# 前序位置if root.val val1 or root.val val2:# 如果遇到目标值直接返回return rootleft self.find(root.left, val1, val2)right self.find(root.right, val1, val2)# 后序位置已经知道左右子树是否存在目标值if left and right:# 当前节点是 LCA 节点return rootreturn left if left else right
在 find 函数的后序位置如果发现 left 和 right 都非空就说明当前节点是 LCA 节点即解决了第一种情况 在 find 函数的前序位置如果找到一个值为 val1 或 val2 的节点则直接返回恰好解决了第二种情况 因为题目说了 p 和 q 一定存在于二叉树中这点很重要所以即便我们遇到 q 就直接返回根本没遍历到 p也依然可以断定 p 在 q 底下q 就是 LCA 节点。
这样标准的最近公共祖先问题就解决了接下来看看这个题目有什么变体。 1676. 二叉树的最近公共祖先 IV
依然给你输入一棵不含重复值的二叉树但这次不是给你输入 p 和 q 两个节点了而是给你输入一个包含若干节点的列表 nodes这些节点都存在于二叉树中让你算这些节点的最近公共祖先。
函数签名如下
def lowestCommonAncestor(root: TreeNode, nodes: List[TreeNode]) - TreeNode:
比如还是这棵二叉树 输入 nodes [7,4,6]那么函数应该返回节点 5。
看起来怪吓人的实则解法逻辑是一样的把刚才的代码逻辑稍加改造即可解决这道题
【python】
class Solution:def lowestCommonAncestor(self, root: TreeNode, nodes: List[TreeNode]) - TreeNode:# 将列表转化成哈希集合便于判断元素是否存在values set()for node in nodes:values.add(node.val)return self.find(root, values)def find(self, root: TreeNode, values: set) - TreeNode:if not root:return None# 前序位置if root.val in values:return rootleft self.find(root.left, values)right self.find(root.right, values)# 后序位置已经知道左右子树是否存在目标值if left and right:# 当前节点是 LCA 节点return rootreturn left if left else right
不过需要注意的是这两道题的题目都明确告诉我们这些节点必定存在于二叉树中如果没有这个前提条件就需要修改代码了。 1644. 二叉树的最近公共祖先 II
给你输入一棵不含重复值的二叉树的以及两个节点 p 和 q如果 p 或 q 不存在于树中则返回空指针否则的话返回 p 和 q 的最近公共祖先节点。
在解决标准的最近公共祖先问题时我们在 find 函数的前序位置有这样一段代码
// 前序位置
if (root.val val1 || root.val val2) {// 如果遇到目标值直接返回return root;
}
我也进行了解释因为 p 和 q 都存在于树中所以这段代码恰好可以解决最近公共祖先的第二种情况 但对于这道题来说p 和 q 不一定存在于树中所以你不能遇到一个目标值就直接返回而应该对二叉树进行完全搜索遍历每一个节点如果发现 p 或 q 不存在于树中那么是不存在 LCA 的。
回想我在文章开头分析的几种 find 函数的写法哪种写法能够对二叉树进行完全搜索来着
这种
def find(root: TreeNode, val: int) - TreeNode:if not root:return None# 先去左右子树寻找left find(root.left, val)right find(root.right, val)# 后序位置判断 root 是不是目标节点if root.val val:return root# root 不是目标节点再去看看哪边的子树找到了return left if left else right
那么解决这道题也是类似的我们只需要把前序位置的判断逻辑放到后序位置即可
【python】
class Solution:def __init__(self):# 用于记录 p 和 q 是否存在于二叉树中self.foundP Falseself.foundQ Falsedef lowestCommonAncestor(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 None# p 和 q 都存在二叉树中才有公共祖先return res# 在二叉树中寻找 val1 和 val2 的最近公共祖先节点def find(self, root, val1, val2):if not root:return Noneleft self.find(root.left, val1, val2)right self.find(root.right, val1, val2)# 后序位置判断当前节点是不是 LCA 节点if left and right:return root# 后序位置判断当前节点是不是目标值if root.val val1 or root.val val2:# 找到了记录一下if root.val val1:self.foundP Trueif root.val val2:self.foundQ Truereturn rootreturn left if left else right
这样改造对二叉树进行完全搜索同时记录 p 和 q 是否同时存在树中从而满足题目的要求。
接下来我们再变一变如果让你在二叉搜索树中寻找 p 和 q 的最近公共祖先应该如何做呢 235. 二叉搜索树的最近公共祖先
给你输入一棵不含重复值的二叉搜索树以及存在于树中的两个节点 p 和 q请你计算 p 和 q 的最近公共祖先节点。
把之前的解法代码复制过来肯定也可以解决这道题但没有用到 BST「左小右大」的性质显然效率不是最高的。
在标准的最近公共祖先问题中我们要在后序位置通过左右子树的搜索结果来判断当前节点是不是 LCA
对于 BST 来说根本不需要老老实实去遍历子树由于 BST 左小右大的性质将当前节点的值与 val1 和 val2 作对比即可判断当前节点是不是 LCA
假设 val1 val2那么 val1 root.val val2 则说明当前节点就是 LCA若 root.val 比 val1 还小则需要去值更大的右子树寻找 LCA若 root.val 比 val2 还大则需要去值更小的左子树寻找 LCA。
依据这个思路就可以写出解法代码
【python】
class Solution:def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) - TreeNode:# 保证 val1 较小val2 较大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: TreeNode, val1: int, val2: int) - TreeNode:if not root:return Noneif root.val val2:# 当前节点太大去左子树找return self.find(root.left, val1, val2)if root.val val1:# 当前节点太小去右子树找return self.find(root.right, val1, val2)# val1 root.val val2# 则当前节点就是最近公共祖先return root 1650. 二叉树的最近公共祖先 III
再看最后一道最近公共祖先的题目吧力扣第 1650 题「二叉树的最近公共祖先 III」这次输入的二叉树节点比较特殊包含指向父节点的指针。题目会给你输入一棵存在于二叉树中的两个节点 p 和 q请你返回它们的最近公共祖先。函数签名如下
class Node:def __init__(self):self.val Noneself.left Noneself.right Noneself.parent None# 函数签名
def lowestCommonAncestor(p: Node, q: Node) - Node:
由于节点中包含父节点的指针所以二叉树的根节点就没必要输入了。
这道题其实不是公共祖先的问题而是单链表相交的问题你把 parent 指针想象成单链表的 next 指针题目就变成了
给你输入两个单链表的头结点 p 和 q这两个单链表必然会相交请你返回相交点。 【python】
class Solution:def lowestCommonAncestor(self, p: Node, q: Node) - Node:# 施展链表双指针技巧a, b p, qwhile a ! b:# a 走一步如果走到根节点转到 q 节点a q if a is None else a.parent# b 走一步如果走到根节点转到 p 节点return a 3、总结
最近公共祖先问题核心在于去理解p和q两个节点所处位置不同引申出来的代码逻辑不同。
class Solution:def __init__(self):# 对于p,q 不确定有无得情况需要额外加变量进行跟踪并将find函数调整为后序遍历方式# 遇到p,q就更新这俩参数self.foundP Falseself.foundQ Falsedef lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) - TreeNode:return self.find(root, p.val, q.val)# 在二叉树中寻找 val1 和 val2 的最近公共祖先节点def find(self, root: TreeNode, val1: int, val2: int) - TreeNode:# 碰到叶子节点返回None即可if not root:return None1、在前序位置遍历到目标值不论是p还是q直接返回该节点其上层函数自有left或right做承接。2、即使给的不是val1和val2而是一个list依然只需判决该 root.val in list 即可返回root。3、若将此判决调到后序位置则find方法会遍历所有节点在不确定p,q是否存在的情况下用起来很方便。4、对于BST的最小公共祖先问题只需明确p qroot.val p就去find右边root.val q就去find左边。if root.val val1 or root.val val2:# 如果遇到目标值直接返回return root# find遍历便利的结果自然需要变量做承接便于后续判决left self.find(root.left, val1, val2)right self.find(root.right, val1, val2)1、后续位置做left and right的判决如果此节点left和right都存在直接起一个截胡效果不用继续向后遍历直接确定该节点就是LCA并返回。2、即使给的不是val1和val2而是一个list即便某个节点的left and right各自只遍历到list中的一个值放心地 return root, 因为自然会有上层函数通过这段代码进行“截胡”依然能正确返回上层那个 left and right 都满足的节点。if left and right:# 当前节点是 LCA 节点return root1、当后序位置的 left and right判决迟迟未响应时这行 return 代码做了最后的兜底。2、即使给的不是val1和val2而是一个list同理直接对该节点进行return也是起一个兜底的效果。return left if left else right
