定制网站开发哪个好,怎么做网页快照,新手如何涨1000粉,营销型网站建设微博Leetcode 654. 最大二叉树
讲解前#xff1a;
这道题其实思路并不难#xff0c;无非就是找到当前数组的最大值作为root节点#xff0c;然后对数组进行切割之后再对左右两个数组进行递归重复操作
class Solution:def constructMaximumBinaryTree(self, nums: List[int]) -…Leetcode 654. 最大二叉树
讲解前
这道题其实思路并不难无非就是找到当前数组的最大值作为root节点然后对数组进行切割之后再对左右两个数组进行递归重复操作
class Solution:def constructMaximumBinaryTree(self, nums: List[int]) - Optional[TreeNode]:# base case when lenght is one create the leaf nodeif len(nums) 1:return TreeNode(nums[0], None, None)# search the current list and find max num and its indexindex 0max_val 0for i, n in enumerate(nums):if n max_val:max_val nindex i# create the new node and have its left and right point# to the recursive callnode TreeNode(max_val)# for left part, make sure we have element leftif index 0:left self.constructMaximumBinaryTree(nums[0: index])node.left left# for right make sure index is not at endif index len(nums) - 1:right self.constructMaximumBinaryTree(nums[index 1: len(nums)])node.right rightreturn node
讲解后
讲解后我打算试一下不用新建数组的方法也就是重新写一个递归函数然后参数中传入的不仅是数组同时也有当前sublist的左右index这样在进行分割操作的时候就只需要修改左右指针了不需要传入一个新的数组
class Solution:def constructMaximumBinaryTree(self, nums: List[int]) - Optional[TreeNode]:def dfs(nums, start, end):# base case when current range only has one elementif start end:return TreeNode(nums[start])# find the max value in current rangeindex 0max_val 0for i in range(start, end 1):if nums[i] max_val:index i max_val nums[i]node TreeNode(max_val)# do the split by modifying the start and endif index start:left dfs(nums, start, index - 1)node.left leftif index end:right dfs(nums, index 1, end)node.right right return nodereturn dfs(nums, 0, len(nums) - 1)
这里我的start和end两个指针一直指向当前遍历的数组部分并且使用的是左闭右闭的思路所以在遍历每一个数字找到最大值的时候range的右边要取到end 1 Leetcode 617. 合并二叉树
讲解前
很烦这道题尝试自己写写了半天没办法写好处理不好递归的call该怎么弄
讲解后
我不能理解为什么我一开始没有这样写我感觉我一开始写的时候的版本其实和这个最像的但是由于某些因素影响出了问题在那之后我就和正确答案越走越远了
class Solution:def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) - Optional[TreeNode]:# base case if not root1 and not root2:return if root1 and not root2:return root1if root2 and not root1:return root2node TreeNode(root1.val root2.val)node.left self.mergeTrees(root1.left, root2.left)node.right self.mergeTrees(root1.right, root2.right)return nodeLeetcode 700. 二叉搜索树搜索
讲解前
我真的好烦不知道为什么还是没办法把这么简答你的题写出来总是掌握不好该返回的值有很多问题很沮丧我每次不会的就是不知道如何才能在遍历到一半发现答案之后就停止遍历然后把答案一层一层的传上去
好吧我脑子出问题了问题在于我的if 条件一开始就写错了明明应该判断val的值是否大于小于当前节点值我弄反了
class Solution:def searchBST(self, root: Optional[TreeNode], val: int) - Optional[TreeNode]:# base case# when we reached the end still not found or # the current node is found if not root or root.val val:return root# recursive caseif val root.val:root self.searchBST(root.left, val)else:root self.searchBST(root.right, val)return root
然后迭代法也非常好写就直接一个while循环去找就行了如果到最后遇到了none的情况就是没找到如果中途找到了就直接return
class Solution:def searchBST(self, root: Optional[TreeNode], val: int) - Optional[TreeNode]:while root:if val root.val:root root.leftelif val root.val:root root.rightelse:return rootreturn None
讲解后
思路和卡哥完全一样没问题
Leetcode 98. 验证二叉搜索树
讲解前
这道题我之前是做过的会比较容易踩的坑就是我们在遍历到每一个root的时候只去在乎当前的left和right是否遵循比root小和大但是忽略了其实整个左右子树中所有的node都需要小于和大于root节点所以我们需要一个区间来通过遍历是进行更新然后用他来限制所有的节点所以我的解法中的left和right就是区间的大小当我们遍历到当前节点之后我们向左和向右遍历的时候向左就可以更新右边的界限把右边设置为当前节点的值代表包括左节点在内的左子树中的所有节点值都应该只比当前节点小右节点同理
class Solution:def isValidBST(self, root: Optional[TreeNode]) - bool:# create a dfs check each node def dfs(root, left, right):# base case:if not root:return True if root.val left or root.val right:return False# update the left and right bound for left node# and right nodeleft dfs(root.left, left, root.val)right dfs(root.right, root.val, right)return left and rightreturn dfs(root, float(-inf), float(inf)) 讲解后
卡哥视频中的思路和我上面的完全不一样他主要是利用了BST的一个特性来解决的问题那就是如果我们对一个BST进行中序遍历那么遍历的顺序加入到一个list里这个list一定是递增的顺序所以这里的思路就是简单的对这个树进行中序遍历过程中利用一个指针来指向上一个node然后我们需要确认当前遍历的node的val永远比上一个node的val大如果错了就直接返回False
class Solution:def isValidBST(self, root: Optional[TreeNode]) - bool:pre TreeNode(float(-inf))def dfs(root):nonlocal preif not root:return Trueleft dfs(root.left)if root.val pre.val:pre rootelse:return False right dfs(root.right)return left and right return dfs(root)
