建站行业的发展前景,网页游戏传奇图片,适合农村的代加工厂,小企业网站建设平台二叉搜索树#xff0c;首先上定义#xff1a;
节点的左子树只包含小于当前节点的数。节点的右子树只包含大于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。
而二叉搜索树最有用的性质就是#xff0c;对其中序遍历可以得到一个递增的有序序列。更多的内容首先上定义
节点的左子树只包含小于当前节点的数。节点的右子树只包含大于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。
而二叉搜索树最有用的性质就是对其中序遍历可以得到一个递增的有序序列。更多的内容可以到这个Leetbook当中学习。
700. 二叉搜索树中的搜索
递归法
class Solution:def searchBST(self, root: TreeNode, val: int) - TreeNode:while root and root.val ! val:root root.left if root.val val else root.rightreturn root迭代法
class Solution:def searchBST(self, root: TreeNode, val: int) - TreeNode:node rootwhile node:if val node.val:node node.leftelif val node.val:node node.rightelse:return nodereturn None简单题目标数值大于当前节点值的话去右子树小于当前节点值的话去左子树直到目标数值等于当前节点值。
701. 二叉搜索树中的插入操作
递归法
class Solution:def insertIntoBST(self, root: TreeNode, val: int) - TreeNode:if not root:return TreeNode(val)if val root.val:root.left self.insertIntoBST(root.left, val)else:root.right self.insertIntoBST(root.right, val)return root 迭代法
class Solution:def insertIntoBST(self, root: TreeNode, val: int) - TreeNode:if not root:return TreeNode(val)node rootwhile node:if val node.val:if node.left:node node.leftelse:node.left TreeNode(val)breakelse:if node.right:node node.rightelse:node.right TreeNode(val)breakreturn root同样的由于二叉搜索树自带大小关系所以一个元素只要根据大小关系迭代进入左右子树找到的空节点即为要插入的节点位置。
450. 删除二叉搜索树中的节点
class Solution:def deleteNode(self, root: Optional[TreeNode], key: int) - Optional[TreeNode]:if not root:return root# 要删除的节点在左子树if key root.val:root.left self.deleteNode(root.left, key)return root# 要删除的节点在右子树elif key root.val:root.right self.deleteNode(root.right, key)return root# 找到了要删除的节点else:# 1、如果节点的左子树为空就用右子树替代它自己if not root.left:return root.right# 2、如果节点的右子树为空就用左子树替代它自己elif not root.right:return root.left# 3、节点的左右子树都不为空则用它的后继节点替代它自己else:cur root.rightwhile cur.left:cur cur.left# 将待删除节点的左子树接到其后继节点的左边然后返回其右子树cur.left root.leftreturn root.right这里有个知识点在中序遍历里面一个节点的前驱节点仅小于待删除节点的节点是其左节点的最右节点右到底一个节点的后继节点仅大于待删除节点的节点是其右节点的最左节点左到底。删除节点分三类情况讨论。
98. 验证二叉搜索树面试题 04.05. 合法二叉搜索树
验证二叉搜索树第一种方法是从定义出发
class Solution:def isValidBST(self, root: TreeNode) - bool:def bounder(lower, node: TreeNode, upper) - bool:if not node:return True val node.valif val lower or val upper:return Falsereturn bounder(lower, node.left, val) and bounder(val, node.right, upper)return bounder(float(-inf), root, float(inf))使用递归函数判断二叉搜素树是否符合定义同时传入边界作为参数。
第二种方法是根据二叉搜索树的性质即中序遍历得到递增序列
class Solution:def isValidBST(self, root: TreeNode) - bool:self.temp float(-inf)self.isValid Truedef inorder(root: TreeNode):if not root:returninorder(root.left) # 左根右if root.val self.temp:self.isValid Falseself.temp root.valinorder(root.right)inorder(root)return self.isValid递归写法要使用到全局变量比较麻烦建议用统一的迭代写法
class Solution:def isValidBST(self, root: TreeNode) - bool:stack []stack.append(root)pre None while stack:node stack.pop()if node:if node.right:stack.append(node.right)stack.append(node)stack.append(None)if node.left:stack.append(node.left)else:node stack.pop()if pre and pre.val node.val:return Falsepre nodereturn True 剑指 Offer 54. 二叉搜索树的第k大节点
class Solution:def kthLargest(self, root: TreeNode, k: int) - int:ans []if not root:return Nonestack []stack.append(root)while stack:node stack.pop()if node:if node.right:stack.append(node.right)stack.append(node)stack.append(None)if node.left:stack.append(node.left)else:node stack.pop()ans.append(node.val)return ans[-k]中序遍历得到递增序列然后取倒数第k个即为第k大的节点值。
230. 二叉搜索树中第K小的元素
class Solution:def kthSmallest(self, root: Optional[TreeNode], k: int) - int:ans []if not root:return Nonestack []stack.append(root)while stack:node stack.pop()if node:if node.right:stack.append(node.right)stack.append(node)stack.append(None)if node.left:stack.append(node.left)else:node stack.pop()ans.append(node.val)return ans[k-1]还是中序遍历由于是取第 k 小所有也可以遍历 k 个节点后直接跳出循环。
530. 二叉搜索树的最小绝对差783. 二叉搜索树节点最小距离
class Solution:def getMinimumDifference(self, root: TreeNode) - int:if not root:return Noneans 100001pre Nonestack []stack.append(root)while stack:node stack.pop()if node:if node.right:stack.append(node.right)stack.append(node)stack.append(None)if node.left:stack.append(node.left)else:node stack.pop()if pre and abs(pre.val - node.val) ans:ans abs(pre.val - node.val)pre nodereturn ans还是中序遍历用 pre 记录前面的节点用 ans 记录最小的相邻数字之差绝对值。
501. 二叉搜索树中的众数
class Solution:def findMode(self, root: TreeNode) - List[int]:if not root:return Noneans []maxCount 0count 0pre Nonestack []stack.append(root)while stack:node stack.pop()if node:if node.right:stack.append(node.right)stack.append(node)stack.append(None)if node.left:stack.append(node.left)else:node stack.pop()# 如果前面有节点且两者的值相同就 count 1否则就是一个新的数if pre and pre.val node.val:count 1else:count 1# 如果当前的数出现次数恰好等于 maxCount那就加到 ans 中if count maxCount:ans.append(node.val)# 如果当前的数出现次数大于 maxCount那就是新的众数elif count maxCount:maxCount countans [node.val]pre nodereturn ans还是中序遍历用 pre 记录前面的节点用 count 记录当前数出现的次数用 maxCount 记录出现最多的数字的出现次数用 ans 记录出现最多的数字可能有多个众数。
235. 二叉搜索树的最近公共祖先剑指 Offer 68 - I. 二叉搜索树的最近公共祖先
class Solution:def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) - TreeNode:node rootwhile node:if p.val node.val and q.val node.val:node node.leftelif p.val node.val and q.val node.val:node node.rightelse:return nodereturn None要找到两个节点的最近公共祖先只需要从根节点开始同时对两个节点进行搜索让他们一起移动直到第一次出现分歧点即为最近公共祖先。
255. 验证前序遍历序列二叉搜索树
class Solution:def verifyPreorder(self, preorder: List[int]) - bool:stack []root float(-inf)for i in range(len(preorder)):if preorder[i] root: # 下一个节点必须比root值大否则返回Falsereturn Falsewhile stack and stack[-1] preorder[i]: # 找到右子树对应的根节点root值下一个节点必须比这个值大root stack.pop()stack.append(preorder[i])return True前序遍历序列就是根左右会先一直遍历左子树到底若是二叉搜索树则必定是个递减序列然后出现第一个比前面的数大的肯定是遍历了右子树本题关键就在此这个右子树不仅要比前一个数左子树大还要比其根节点父节点大。因此用一个栈记录遍历过的前序序列递减时正常记录每当出现递增的时候都要找到前面序列中仅次于右子树的值根节点再后一个值是必须大于这个值的否则返回False。
剑指 Offer 33. 二叉搜索树的后序遍历序列
class Solution:def verifyPostorder(self, postorder: List[int]) - bool:stack []root float(inf)for i in range(len(postorder) - 1, -1, -1):if postorder[i] root:return Falsewhile stack and stack[-1] postorder[i]: root stack.pop()stack.append(postorder[i])return True与上一题类似后序遍历是左右根序列是先递增再递减还是在递增转折为递减的时候判断转折节点与其根节点的关系。推荐题解看这篇。
1008. 前序遍历构造二叉搜索树
class Solution:def bstFromPreorder(self, preorder: List[int]) - TreeNode:if preorder:leftTree []rightTree []root TreeNode(preorder.pop(0))for val in preorder:if val root.val:rightTree.append(val)else:leftTree.append(val)root.left self.bstFromPreorder(leftTree)root.right self.bstFromPreorder(rightTree)return root从前序遍历序列构造二叉搜索树思路就是递归利用二叉搜索树的特点将小于当前节点的作为左子树大于当前节点的作为右子树即可。
95. 不同的二叉搜索树 II
class Solution:def generateTrees(self, n: int) - List[TreeNode]:def helper(start, end):if start end:return [None]allTrees []for i in range(start, end1):leftTrees helper(start, i-1)rightTrees helper(i1, end)for l in leftTrees:for r in rightTrees:curTree TreeNode(i)curTree.left lcurTree.right rallTrees.append(curTree)return allTreesreturn helper(1, n) if n else []我们定义 helper(start, end) 函数表示当前值的集合为 [start,end]返回序列 [start,end] 生成的所有可行的二叉搜索树。在每次递归中我们枚举 [start,end] 中的值 i 为当前二叉搜索树的根那么序列划分为了 [start,i−1] 和 [i1,end] 两部分。我们递归调用这两部分即 helper(start, i - 1) 和 helper(i 1, end)获得所有可行的左子树和可行的右子树那么最后一步我们只要从可行左子树集合中选一棵再从可行右子树集合中选一棵拼接到根节点上并将生成的二叉搜索树放入答案数组即可。
递归的入口即为 helper(1, n)出口为当 start end 的时候当前二叉搜索树为空返回空节点即可。
173. 二叉搜索树迭代器
这题最简单的思路是在__init__的时候进行一次中序遍历把二叉搜索树的递增序列用队列记录下来然后在next的时候返回队列首部的元素 popleft 即可。
class BSTIterator(object):def __init__(self, root):self.queue collections.deque()self.inOrder(root)def inOrder(self, root):if not root: returnself.inOrder(root.left)self.queue.append(root.val)self.inOrder(root.right)def next(self):return self.queue.popleft()def hasNext(self):return len(self.queue) 0更好的思路是迭代法
class BSTIterator:def __init__(self, root: TreeNode):self.stack []while root:self.stack.append(root)root root.leftdef next(self) - int:cur self.stack.pop()node cur.rightwhile node:self.stack.append(node)node node.leftreturn cur.valdef hasNext(self) - bool:return len(self.stack) 0对比中序遍历的迭代写法可以发现迭代器实际上是把中序遍历拆开分别执行了 # 中序遍历def inorderTraversal(self, root: TreeNode) - List[int]:ans list()if not root:return ans stack list()node rootwhile stack or node:while node: # 当node的左子节点为空时停止stack.append(node)node node.left
###########################################################node stack.pop() # 回溯ans.append(node.val)node node.right # 访问右子节点 return ans在__init__的时候执行到了上半部分之后每次next都会执行本次循环的下半部分和下一次循环的上半部分即相当于用手动的next代替了while stack or node。
二叉搜索树主要支持三个操作搜索、插入和删除。二叉搜索树的优点是即便在最坏的情况下也允许你在O(h)的时间复杂度内执行所有的搜索、插入、删除操作。通常来说如果你想有序地存储数据或者需要同时执行搜索、插入、删除等多步操作二叉搜索树这个数据结构是一个很好的选择。
938. 二叉搜索树的范围和
class Solution:def rangeSumBST(self, root: TreeNode, low: int, high: int) - int:def inorder(node: TreeNode):if not node:returnif node.val low:inorder(node.left)if node.val high and node.val low:self.counter node.valif node.val high:inorder(node.right)self.counter 0inorder(root)return self.counter中序遍历二叉搜索树只要节点值在范围内即累计到答案中优化了的地方是当前节点值大于左边界才去遍历左子树否则左子树都是比左边界小越界小于右边界才去遍历右子树否则右子树都是比右边界大越界。
669. 修剪二叉搜索树
class Solution:def trimBST(self, root: TreeNode, low: int, high: int) - TreeNode:def trim(node):if not node:return Noneelif node.val high: # 若当前节点值大于high则它的右子树必大于highreturn trim(node.left)elif node.val low: # 若当前节点值小于low则它的左子树必小于lowreturn trim(node.right)else:node.left trim(node.left)node.right trim(node.right)return nodereturn trim(root)修剪的方法就是如果当前节点值大于high则它的右子树必大于high只能返回其左子树如果当前节点值小于low则它的左子树必小low只能返回其右子树。注意增加return node是因为根节点可能改变否则就 trim(root) 然后 return root 就行了。
285. 二叉搜索树中的中序后继剑指 Offer II 053. 二叉搜索树中的中序后继面试题 04.06. 后继者
class Solution:def inorderSuccessor(self, root: TreeNode, p: TreeNode) - TreeNode:if p.right:p p.rightwhile p.left:p p.leftreturn pstack []node rootpre float(-inf)while stack or node:while node:stack.append(node)node node.leftnode stack.pop()if pre p.val: return nodepre node.val node node.rightreturn None对于有右子树的节点它的后继节点递增序列中右边的元素是其右节点的最左节点左到底。如果没有右子树则其后继节点是其作为左子树时的父节点。如果节点即没有右子树其自身又是右子树则没有后继节点。
510. 二叉搜索树中的中序后继 II
class Solution:def inorderSuccessor(self, node: Node) - Node:if node.right:node node.rightwhile node.left:node node.leftreturn nodeelse:while node.parent and node node.parent.right:node node.parentreturn node.parent本题的条件比上一题修改了一点没有了根节点但是多了父节点指针。思路还是一样如果节点有右子树其后继节点可以马上找到如果没有则寻找其父节点、父节点的父节点一直到找到有父子关系是右子树的或者空节点为止。
653. 两数之和 IV - 输入 BST剑指 Offer II 056. 二叉搜索树中两个节点之和
class Solution:def findTarget(self, root: TreeNode, k: int) - bool:def inorder(node: TreeNode):if not node:return inorder(node.left)nums.append(node.val)inorder(node.right)nums []inorder(root)left 0right len(nums) - 1while left right:if nums[left] nums[right] k:return Trueelif nums[left] nums[right] k:right - 1else:left 1return False还是先用中序遍历记录数组得到递增序列然后用双指针即可。
1214. 查找两棵二叉搜索树之和
class Solution:def twoSumBSTs(self, root1: TreeNode, root2: TreeNode, target: int) - bool: def inorder(node: TreeNode, nums):if not node:return inorder(node.left, nums)nums.append(node.val)inorder(node.right, nums)nums1, nums2 [], []inorder(root1, nums1)inorder(root2, nums2) left 0right len(nums2) - 1while left len(nums1) and 0 right:if nums1[left] nums2[right] target:return Trueelif nums1[left] nums2[right] target:right - 1else:left 1return False与上一题类似此题是要在两个二叉搜索树中找到两数之和即做两次中序遍历然后双指针分别遍历两个递增序列即可。
897. 递增顺序搜索树剑指 Offer II 052. 展平二叉搜索树面试题 17.12. BiNode
class Solution:def increasingBST(self, root: TreeNode) - TreeNode:if not root:return Nonestack []node rootnewnode 0while stack or node:while node:stack.append(node)node node.leftnode stack.pop()if newnode 0: # 第一个节点newnode TreeNode(node.val)newroot newnodeelse:newnode.right TreeNode(node.val)newnode newnode.rightnode node.rightreturn newroot在中序遍历二叉搜索树的同时用一个新的节点构建二叉树即可。
99. 恢复二叉搜索树
class Solution:def recoverTree(self, root: Optional[TreeNode]) - None:firstNode NonesecondNode Nonepre TreeNode(float(-inf))stack []node rootwhile node or stack:while node:stack.append(node)node node.leftnode stack.pop()if pre.val node.val:if not firstNode:firstNode preif firstNode: secondNode nodepre nodenode node.rightfirstNode.val, secondNode.val secondNode.val, firstNode.val中序遍历二叉搜索树得到的一定是递增序列如果有两个节点被错误交换则反映在序列中一定是出现了递减的位置找到这两个位置即可。
108. 将有序数组转换为二叉搜索树
class Solution:def sortedArrayToBST(self, nums: List[int]) - Optional[TreeNode]:n len(nums)if n 0:return Nonemid n // 2root TreeNode(nums[mid])root.left self.sortedArrayToBST(nums[:mid])root.right self.sortedArrayToBST(nums[mid1:])return root最直观的思路每次取中间元素作为当前的根节点两侧的元素作为左右子树递归建树左侧区间 [:mid-1] 作为左子树右侧区间 [mid1:] 作为右子树。如果想节省点空间那递归时用区间的指针代替区间也可以
class Solution:def sortedArrayToBST(self, nums: List[int]) - Optional[TreeNode]:def helper(left, right):if left right:return Nonemid (left right) // 2root TreeNode(nums[mid])root.left helper(left, mid - 1)root.right helper(mid 1, right)return rootreturn helper(0, len(nums) - 1)538. 把二叉搜索树转换为累加树1038. 把二叉搜索树转换为累加树剑指 Offer II 054. 所有大于等于节点的值之和
递归法
class Solution:def convertBST(self, root: Optional[TreeNode]) - Optional[TreeNode]:total 0def inorder(root: TreeNode):nonlocal totalif not root:returninorder(root.right)total root.valroot.val totalinorder(root.left)inorder(root)return root迭代法
class Solution:def convertBST(self, root: Optional[TreeNode]) - Optional[TreeNode]:if not root:return Nonestack []stack.append(root)total 0while stack:node stack.pop()if node:if node.left:stack.append(node.left)stack.append(node)stack.append(None)if node.right:stack.append(node.right)else:node stack.pop()total node.valnode.val totalreturn root本题要求我们将每个节点的值修改为原来的节点值加上所有大于它的节点值之和。我们只需要反序中序遍历该二叉搜索树即右根左记录过程中的节点值之和并不断更新当前遍历到的节点的节点值即可得到题目要求的累加树。
426. 将二叉搜索树转化为排序的双向链表剑指 Offer 36. 二叉搜索树与双向链表
class Solution:def treeToDoublyList(self, root: Node) - Node:if not root:return Nonedef inorder(node):nonlocal first, lastif not node:returninorder(node.left)if not first:first nodeelse:last.right nodenode.left lastlast nodeinorder(node.right)first, last None, Noneinorder(root)last.right firstfirst.left lastreturn first使用两个指针一个头指针一个尾指针初始均为空。然后中序遍历二叉搜索树如果头指针为空则把该节点设为头节点否则就先建立当前节点与下一个节点的双向联系然后移动到下一个节点。遍历完成后再补上尾节点与头节点的联系即可。
