网站制作报价开,js跳转到别的网站,上海网站开发企业,如何设定旅游网站seo核心关键词Leetcod面试经典150题刷题记录-系列Leetcod面试经典150题刷题记录——数组 / 字符串篇Leetcod面试经典150题刷题记录 —— 双指针篇Leetcod面试经典150题刷题记录 —— 矩阵篇Leetcod面试经典150题刷题记录 —— 滑动窗口篇Leetcod面试经典150题刷题记录 —— 哈希表篇Leetcod面…Leetcod面试经典150题刷题记录-系列Leetcod面试经典150题刷题记录——数组 / 字符串篇Leetcod面试经典150题刷题记录 —— 双指针篇Leetcod面试经典150题刷题记录 —— 矩阵篇Leetcod面试经典150题刷题记录 —— 滑动窗口篇Leetcod面试经典150题刷题记录 —— 哈希表篇Leetcod面试经典150题刷题记录 —— 区间篇Leetcod面试经典150题刷题记录——栈篇Leetcod面试经典150题刷题记录——链表篇Leetcod面试经典150题刷题记录——二叉树篇Leetcod面试经典150题刷题记录——二叉树层次遍历篇Leetcod面试经典150题刷题记录——二叉搜索树篇 Leetcod面试经典150题刷题记录 —— 二叉搜索树篇 二叉搜索树性质1. 二叉搜索树的最小绝对差脏乱差版本优雅版本 2. 二叉搜索树中第K小的元素3. 验证二叉搜索树经典错误(从局部性质推断全局性质)利用第1题的代码(有pre指针的那段) 遇到二叉搜索树(BST)的题目一旦用了sort()直接挂掉面试切记
二叉搜索树性质 二叉搜索树的性质满足 (1)左节点 root 右节点 (局部性质) (2)左子树所有节点 root 右子树所有节点 (全局性质该性质包括局部性质所以更重要) 相当部分程序员写起上面的局部性质很容易写全局性质的判断就容易犯病不瞒你说我也是。 1. 二叉搜索树的最小绝对差 题目链接二叉搜索树的最小绝对差 - leetcode 题目描述 给你一个二叉搜索树的根节点 root 返回 树中任意两不同节点值之间的最小差值 。差值是一个正数其数值等于两值之差的绝对值。 题目归纳 解题思路 解法 验证二叉搜索树 - leetcode官方题解 脏乱差版本
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right# 返回二叉搜索树中任意两个不同节点值之间的最小差值
# 性质
# (1)二叉搜索树。题目既然说了那么肯定要用到该性质
# (2)任意两个不同节点值强调了任意两个不同节点。但是既然是二叉搜索树了拿右子树中的节点 - 左子树中的节点肯定不会是答案所以这里的任意其实是带引号的任意不是绝对的任意是可以忽略一些情况的任意# 以root节点为例要查找的目标点一定是下面两种情况
# (1)左树的最右节点 左树的最大节点 中序遍历的前驱pre节点
# (2)右树的最左节点 右树的最大节点 中序遍历的后继post节点
# 最后递归搜索
class Solution:def getMinDistance(self, root: Optional[TreeNode]) - int:if not root: return 0# (1)查找左树的最右节点 左树的最大节点LR root.leftwhile LR and (LR.left or LR.right):# 有右边找右边没右边找左边再找右边if LR.right:LR LR.rightelse:break# (2)查找右树的最左节点 右树的最大节点RL root.rightwhile RL and (RL.left or RL.right):if RL.left:RL RL.leftelse:breakleft_result 1e9if LR: left_result abs(root.val-LR.val)right_result 1e9if RL: right_result abs(root.val-RL.val)return min(left_result, right_result)def getMinimumDifference(self, root: Optional[TreeNode]) - int:result 1e9# 逐个遍历queue deque([root])while queue:size len(queue)for i in range(size):node queue.popleft() if node.left: queue.append(node.left)if node.right: queue.append(node.right)dis self.getMinDistance(node)result min(result, dis)return result优雅版本
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution:def __init__(self):self.result float(inf)self.pre Nonedef traversal(self, cur):if cur is None:return Noneself.traversal(cur.left) # 左if self.pre: # 中self.result min(self.result, cur.val - self.pre.val)self.pre cur # 记录前一个self.traversal(cur.right) # 右def getMinimumDifference(self, root):self.traversal(root)return self.result2. 二叉搜索树中第K小的元素 题目链接二叉搜索树中第K小的元素 - leetcode 题目描述 给定一个二叉搜索树的根节点 root 和一个整数 k 请你设计一个算法查找其中第 k 个最小元素从 1 开始计数。 题目归纳 中序遍历BST成有序数组然后再找到这个有序数组的第k个元素NoNoNo。掌握递归转换成迭代的关键思想即将函数调用栈明写在代码里。 解题思路 解法 二叉搜索树中第K小的元素 - leetcode官方题解 中序遍历的迭代写法注意非递归 # Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right# 这道题掌握两个知识点
# (1)中序遍历的迭代写法。即将函数调用栈明示出来因为函数调用栈也是个栈所有的递归写法都是可以转换为迭代版写法的手动模拟函数调用栈即可。
# (2)二叉搜索树的中序遍历是有序的。class Solution:def kthSmallest(self, root: Optional[TreeNode], k: int) - int:# 中序遍历迭代版而非递归stack []while root or stack:# 相当于递归版写法的左子树遍历while root: # 压栈方向是单一的沿着二叉树的右上角-左下角方向压栈stack.append(root)root root.leftroot stack.pop() # 遇到空就出栈# if root: print(root.val)k - 1if k 0:return root.valroot root.right3. 验证二叉搜索树 题目链接验证二叉搜索树 - leetcode 题目描述 给定一个二叉树的 根节点 root想象自己站在它的右侧按照从顶部到底部的顺序返回从右侧所能看到的节点值。 题目归纳 右视图 右边的侧视图 解题思路 解法 验证二叉搜索树 - leetcode官方题解 (1) 从左到右层序遍历。记录层序遍历的最后一个node即为右视图看到的第一个node。 经典错误(从局部性质推断全局性质)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution:def isValidBST(self, root: Optional[TreeNode]) - bool:# 这是一道21年的408考研真题空节点和叶节点都是二叉搜索树# 注意下面的写法是错误的原因在于只判断了局部的性质而忽略了全局的性质if not root: return Trueif not root.left and not root.right: return True# (1)这个时候root肯定存在左树或许存在结合root与左树根节点判断是不是二叉搜索树if root and root.left and root.left.val root.val:return self.isValidBST(root.left)else:return False# (2)这个时候root肯定存在右树或许存在结合root与右树根节点判断是不是二叉搜索树if root and root.right and root.val root.right.val:return self.isValidBST(root.right)else:return False
利用第1题的代码(有pre指针的那段)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution:def __init__(self):self.pre Nonedef isValidBST(self, root: Optional[TreeNode]) - bool:if not root:return Trueleft self.isValidBST(root.left)if self.pre and self.pre.val root.val: # __比第1题加了这个判断__return Falseself.pre root # 要遍历root.right了这个时候记录pre节点right self.isValidBST(root.right)return left and right # 两边都要是BST树
