二叉搜索树是一个有序树:每个二叉树都满足左子树上所有节点的值均小于它的根节点的值,右子树上所有节点的值均大于它的根节点的值;利用该性质,可以实现二叉搜索树特有的自顶向下遍历
700. 二叉搜索树中的搜索
思路1、自顶向下的遍历:利用二叉搜索树有序性的性质,直接迭代法求解
思路2、递归-重复逻辑:对每个二叉树根节点判断值是否相等、根据值大小关系搜索左右子树
'''
700. 二叉搜索树中的搜索
给定二叉搜索树(BST)的根节点root和一个整数值val。
你需要在 BST 中找到节点值等于val的节点。 返回以该节点为根的子树。 如果节点不存在,则返回null。
示例 1:输入:root = [4,2,7,1,3], val = 2输出:[2,1,3]
思路1、自顶向下的遍历:利用二叉搜索树有序性的性质,直接迭代法求解
思路2、递归-重复逻辑:对每个二叉树根节点判断值是否相等、根据值大小关系搜索左右子树
'''
class Solution:# 利用二叉搜索树有序性的性质,直接迭代法求解def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:while root != None:if root.val > val:root = root.leftelif root.val < val:root = root.rightelse: # root.val == valreturn rootreturn None# 递归-重复逻辑:对每个二叉树根节点判断值是否相等、根据值大小关系搜索左右子树def searchBSTRecursive(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:# 简单情况if root == None:return Noneelif root.val == val:return root# 重复逻辑elif root.val > val:return self.searchBSTRecursive(root.left, val)elif root.val < val:return self.searchBSTRecursive(root.right, val)
235. 二叉搜索树的最近公共祖先
思路:和 “700. 二叉搜索树中的搜索”是一样的题,后者是寻找一个数找到并返回以该数为根节点的子树,本题是寻找同时包含两个数的子树
从上到下的遍历:利用二叉搜索树有序性的性质,只要从上到下遍历的时候,cur节点是数值在[p, q]区间中则说明该节点cur就是最近公共祖先了
递归:重复操作:对每个二叉树根节点判断值是否在[p, q]区间、根据值大小关系搜索左右子树
'''
235. 二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
示例 1:输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8输出: 6 解释: 节点 2 和节点 8 的最近公共祖先是 6。
思路:和 “700. 二叉搜索树中的搜索”是一样的题,后者是寻找一个数找到并返回以该数为根节点的子树,本题是寻找同时包含两个数的子树
从上到下的遍历:利用二叉搜索树有序性的性质,只要从上到下遍历的时候,cur节点是数值在[p, q]区间中则说明该节点cur就是最近公共祖先了。
递归:重复操作:对每个二叉树根节点判断值是否在[p, q]区间、根据值大小关系搜索左右子树
'''
class Solution:def lowestCommonAncestor(self, root: Optional[TreeNode], p: Optional[TreeNode], q: Optional[TreeNode]) -> Optional[TreeNode]:while root != None:if root.val > p.val and root.val > q.val:root = root.leftelif root.val < p.val and root.val < q.val:root = root.rightelse: # 包含了很多种情况(p、q哪个大或小),总体来说就是cur节点是数值在[p, q]区间中,是同时包含这两个数的子树return rootreturn None