给网站做seo的价格,免费的推广平台有哪些,为进一步加强网站建设,前端做的比较好的网站目录#xff1a;
目的
思路
复杂度
记忆秘诀
python代码 目的#xff1a; 给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2#xff0c;请找o1 和 o2 的最近公共祖先节点。 思路 这个任务目和上一题在二叉搜索树中找到两个节点的最近公共祖先有点类…目录
目的
思路
复杂度
记忆秘诀
python代码 目的 给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2请找o1 和 o2 的最近公共祖先节点。 思路 这个任务目和上一题在二叉搜索树中找到两个节点的最近公共祖先有点类似都是找最近公共祖先。但是区别在于一个有序一个无序。 力扣刷题TOP101: 30.BM37 二叉搜索树的最近公共祖先-CSDN博客
特点普通二叉树二叉搜索树数据结构特性无排序特性任意结构左小右大具有排序特性算法实现深度优先搜索(DFS)逐层递归利用节点值逐层比较不需要完整遍历时间复杂度O(n)需要访问所有节点O(h)只需沿着路径查找适用范围任意二叉树仅适用于二叉搜索树效率较低较高 代码逻辑 如果当前节点为空 说明这里没有要找的两个节点直接返回 -1 表示没有找到。 如果当前节点就是其中一个目标节点 说明当前节点可能是最近公共祖先或者它是两个节点之一直接返回当前节点的值。 递归查找左右子树 递归地查找左子树看是否能找到目标节点之一。如果找到了返回对应的值如果没找到返回 -1。递归地查找右子树看是否能找到目标节点之一。如果找到了返回对应的值如果没找到返回 -1。 根据左右子树的结果判断 如果左子树没找到返回 -1说明两个节点都在右子树直接返回右子树的结果。如果右子树没找到返回 -1说明两个节点都在左子树直接返回左子树的结果。如果左右子树都找到了目标节点说明当前节点是它们的最近公共祖先直接返回当前节点的值。 示例假设有以下二叉树目标是找到节点 4 和 5 的最近公共祖先 1/ \2 3/ \4 5递归过程 从根节点 1 开始 左子树递归去节点 2 中查找。右子树递归去节点 3 中查找。 节点 2 的子树 左子树递归在节点 4 找到目标节点 4。右子树递归在节点 5 找到目标节点 5。左右子树都找到目标返回节点 2 作为最近公共祖先。 节点 3 的子树 左右子树递归都为空返回 -1。 回到根节点 1 左子树返回节点 2。右子树返回 -1。因为只有左子树找到目标最终结果是节点 2。 复杂度 时间复杂度O(n 这是一个典型的 深度优先搜索DFS每个节点在递归过程中最多会被访问一次。 空间复杂度O(h) 最坏情况下链表形式的树O(h), 其中 h 是树的高度。最佳情况下完全平衡的树O(logh)。 记忆秘诀 子树为空返回无结果当前节点是目标节点返回自己 递归查找左右子树 两边都找到当前节点是答案 只找到一边继续返回那边结果。 python代码
class TreeNode:def __init__(self, x):self.val xself.left Noneself.right Noneclass Solution:def lowestCommonAncestor(self , root: TreeNode, o1: int, o2: int) - int:# 该子树没找到返回-1if not root:return -1# 该节点是其中某一个节点if root.val o1 or root.val o2:return root.val# 左子树寻找公共祖先left self.lowestCommonAncestor(root.left, o1, o2)# 右子树寻找公共祖先right self.lowestCommonAncestor(root.right, o1, o2)# 左子树为没找到则在右子树中if left -1:return right# 右子树没找到则在左子树中if right -1:return left# 否则是当前节点return root.val* 欢迎大家探讨新思路能够更好的理解和记忆
