网站建设脚本,个人主页背景图,工程造价信息网官网查询,湖州企业网站开发公司相关推荐 python coding with ChatGPT 打卡第12天| 二叉树#xff1a;理论基础 python coding with ChatGPT 打卡第13天| 二叉树的深度优先遍历 python coding with ChatGPT 打卡第14天| 二叉树的广度优先遍历 python coding with ChatGPT 打卡第15天| 二叉树#xff1a;翻转…相关推荐 python coding with ChatGPT 打卡第12天| 二叉树理论基础 python coding with ChatGPT 打卡第13天| 二叉树的深度优先遍历 python coding with ChatGPT 打卡第14天| 二叉树的广度优先遍历 python coding with ChatGPT 打卡第15天| 二叉树翻转二叉树、对称二叉树 python coding with ChatGPT 打卡第16天| 二叉树完全二叉树、平衡二叉树、二叉树的所有路径、左叶子之和 python coding with ChatGPT 打卡第17天| 二叉树找树左下角的值、路径总和 python coding with ChatGPT 打卡第18天| 二叉树从中序与后序遍历序列构造二叉树、最大二叉树 python coding with ChatGPT 打卡第19天| 二叉树合并二叉树 python coding with ChatGPT 打卡第20天| 二叉搜索树搜索、验证、最小绝对差、众数 文章目录 二叉树的最近公共祖先Key Points相关题目视频讲解重点分析 二叉搜索树的最近公共祖先Key Points相关题目视频讲解重点分析 二叉树的最近公共祖先
Key Points
后序遍历左右中就是天然的回溯过程可以根据左右子树的返回值来处理中节点的逻辑。判断逻辑是 如果递归遍历遇到q就将q返回遇到p 就将p返回那么如果 左右子树的返回值都不为空说明此时的中节点一定是q 和p 的最近祖先。
相关题目
236. 二叉树的最近公共祖先
视频讲解
自底向上查找有点难度
重点分析
方法一递归法
递归的终止条件
遇到空的话因为树都是空了所以返回空。如果 root q或者 root p说明找到 q p 则将其返回这个返回值后面在中节点的处理过程中会用到
单层处理逻辑
如果left 和 right都不为空说明此时root就是最近公共节点。这个比较好理解如果left为空right不为空就返回right说明目标节点是通过right返回的反之依然。
def lowestCommonAncestor(root, p, q):if not root:return rootif root p or root q:return rootleft lowestCommonAncestor(root.left, p, q)right lowestCommonAncestor(root.right, p, q)if left and right:return rootif left:return leftif right:return rightreturn None评价 直接使用一次遍历来找到最近公共祖先会更高效。这种方法不需要存储所有父节点的路径而是利用递归在回溯过程中直接找到LCA。
方法二递归法 首先为每个节点找到其所有的父节点然后比较这两个列表来找到最近的公共父节点
def find_all_father(root, p):res []def find_father(root, p):if not root:return Falseif root p or find_father(root.left, p) or find_father(root.right, p):res.append(root)return Truereturn Falsefind_father(root, p)return resdef lowestCommonAncestor(root, p, q):res1 find_all_father(root, p)res2 find_all_father(root, q)for i in res1:for j in res2:if i j:return i评价 对于每个节点p和q你的方法都会遍历整棵树来找到它们的所有父节点。这意味着树被遍历了两次。此外对于找到的每对父节点你使用了双层循环来比较它们这会导致效率低下尤其是在大树上。
方法三迭代法
def lowestCommonAncestor(root, p, q):# 字典用于保存每个节点的父节点parent {root: None}stack [root]# 迭代遍历树直到找到p和qwhile p not in parent or q not in parent:node stack.pop()if node.left:parent[node.left] nodestack.append(node.left)if node.right:parent[node.right] nodestack.append(node.right)# 通过父节点字典构建p到根节点的路径ancestors set()while p:ancestors.add(p)p parent[p]# 检查q到根节点的路径中第一个出现在p路径集合中的节点while q not in ancestors:q parent[q]return q这个代码首先使用一个栈和一个字典来迭代遍历整棵树并记录每个节点的父节点。然后它构建了从p到根节点的路径并保存在一个集合中。最后它追溯q到根节点的路径直到找到第一个也出现在p的路径集合中的节点。这个节点就是p和q的最近公共祖先。
评价 这个方法避免了递归但需要额外的存储空间来记录父节点信息并且需要两次遍历一次是构建父节点的映射一次是构建从目标节点到根节点的路径。
二叉搜索树的最近公共祖先
Key Points
在二叉搜索树BST中找到两个指定节点的最近公共祖先LCA比在普通二叉树中要简单因为你可以利用BST的性质对于任何节点左子树上的所有节点的值都小于该节点的值右子树上的所有节点的值都大于该节点的值。这个性质允许我们使用迭代或递归的方式来快速定位LCA而不需要像在普通二叉树中那样存储父节点或递归遍历整个树。
相关题目
235. 二叉搜索树的最近公共祖先
视频讲解
二叉搜索树找祖先
重点分析
方法一递归
def lowestCommonAncestor(root, p, q):if p.val root.val and q.val root.val:return lowestCommonAncestor(root.right, p, q)if p.val root.val and q.val root.val:return lowestCommonAncestor(root.left, p, q)return root方法二迭代法
def lowestCommonAncestor(root, p, q):while root:if p.val root.val and q.val root.val:root root.leftelif p.val root.val and q.val root.val:root root.rightelse:return root
