东莞网站设计师,酒类网站建设策划书,山西手机响应式网站建设,现在建设网站挣钱吗*654.最大二叉树
题目链接/文章讲解#xff1a;https://programmercarl.com/0654.%E6%9C%80%E5%A4%A7%E4%BA%8C%E5%8F%89%E6%A0%91.html 视频讲解#xff1a;https://www.bilibili.com/video/BV1MG411G7ox
考点 前序遍历构建二叉树 我的思路 参考了力扣题目里的提示递归三要…*654.最大二叉树
题目链接/文章讲解https://programmercarl.com/0654.%E6%9C%80%E5%A4%A7%E4%BA%8C%E5%8F%89%E6%A0%91.html 视频讲解https://www.bilibili.com/video/BV1MG411G7ox
考点 前序遍历构建二叉树 我的思路 参考了力扣题目里的提示递归三要素 形参数值列表返回值当前节点退出条件若数值列表为空返回None递归逻辑 对数值列表求最大值并基于最大值创建当前节点利用最大值的索引切割数值列表并以切割得到的左数值列表作为参数执行左递归生成左子树利用最大值的索引切割数值列表并以切割得到的右数值列表作为参数执行右递归生成右子树 视频讲解关键点总结 和我的思路一致二叉树构造类型的问题要使用前序遍历先构建中间节点 我的思路的问题 无 代码书写问题 无 可执行代码
class Solution:def constructMaximumBinaryTree(self, nums: List[int]) - Optional[TreeNode]:if not nums:return Noneindex 0max_value -1for i in range(len(nums)):if nums[i] max_value:max_value nums[i]index iroot TreeNode(max_value)root.left self.constructMaximumBinaryTree(nums[:index])root.right self.constructMaximumBinaryTree(nums[index 1:])return root617.合并二叉树
题目链接/文章讲解https://programmercarl.com/0617.%E5%90%88%E5%B9%B6%E4%BA%8C%E5%8F%89%E6%A0%91.html 视频讲解https://www.bilibili.com/video/BV1m14y1Y7JK
考点 前序遍历二叉树构建 我的思路 递归三要素 形参两棵树的当前节点返回值为新树的当前节点退出条件如果两棵树的当前节点均为空则返回None递归逻辑 由于本题当两个二叉树节点状态不同执行的逻辑会不同因此接着退出条件的if继续写elif1号二叉树节点为空2号不为空则当前节点基于2号树节点创建同时执行左右递归1号二叉树的位置直接放None生成当前节点的左右节点elif2号二叉树节点为空1号不为空则当前节点基于1号树节点创建同时执行左右递归2号二叉树的位置直接放None生成当前节点的左右节点else1号2号都不为空则当前节点基于二者和创建同时执行左右递归生成当前节点的左右节点返回当前节点 视频讲解关键点总结 可以对上述思路进行优化对于退出条件和两个elif判断可优化为依次判断1号树节点和2号树节点是否为空如果1号为空直接返回2号节点如果2号为空直接返回1号节点因为2者中一旦其一为空则其后续也为空此时新树的后续节点和老树里不为空的那个完全一致 我的思路的问题 可优化逻辑优化思路见上 代码书写问题 无 可执行代码
class Solution:def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) - Optional[TreeNode]:if not root1:return root2if not root2:return root1root TreeNode(root1.val root2.val)root.left self.mergeTrees(root1.left, root2.left)root.right self.mergeTrees(root1.right, root2.right)return root700.二叉搜索树中的搜索
题目链接/文章讲解: https://programmercarl.com/0700.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E6%90%9C%E7%B4%A2.html 视频讲解https://www.bilibili.com/video/BV1wG411g7sF
考点 二叉搜索树的性质二叉树遍历 我的思路 直接进行搜索未利用二叉搜索树的性质 视频讲解关键点总结 利用二叉搜索树的性质在递归逻辑里当val大于当前节点的值时向右子树搜索小于时向左子树搜索 我的思路的问题 为考虑二叉搜索树的性质 代码书写问题 无 可执行代码
class Solution:def searchBST(self, root: Optional[TreeNode], val: int) - Optional[TreeNode]:if root is None:return Noneif root.val val:return rootif root.val val:return self.searchBST(root.left, val)else:return self.searchBST(root.right, val)*98.验证二叉搜索树
题目链接/文章讲解https://programmercarl.com/0098.%E9%AA%8C%E8%AF%81%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html 视频讲解https://www.bilibili.com/video/BV18P411n7Q4
考点 二叉搜索树的特性中序遍历双指针 我的思路 思路较为混乱 视频讲解关键点总结 利用中序遍历和二叉搜索树的特性把题目简化为只需要判断前序遍历过程中前后两个节点是否是后者大于前者即可一种做法是定义一个额外的数组在中序遍历的过程中把所有的值加到数组中之后判断数组是否是个递增数组第二种做法是在递归过程中维护一个表示上一节点值的变量并在每次递归时把当前节点与其相比第三种做法是双指针一个指针指向上一节点另一指针为当前节点 给Solution类初始化一个pre指针递归三要素 形参当前节点返回值为True或False退出条件若当前节点为空return True因为如果是空二叉树也是二叉搜索树递归逻辑 中序遍历左左递归并接收其返回值中如果pre指针不为空且当前节点的值小于等于之前指针的值return False否则把当前节点赋给pre指针右右递归并接收其返回值如果左右递归返回值都为True则返回True否则返回False 我的思路的问题 无思路 代码书写问题 无 可执行代码
class Solution:def __init__(self):self.pre Nonedef isValidBST(self, root: Optional[TreeNode]) - bool:if root is None:return Trueleft self.isValidBST(root.left)if self.pre is not None and self.pre.val root.val:return Falseelse:self.pre rootright self.isValidBST(root.right)return left and right
