杭州 高端网站建设,嘉兴做网站的哪家好,wordpress怎么做网盘收索,网站开发都用什么数据库二叉搜索树是一个有序树#xff1a;每个二叉树都满足左子树上所有节点的值均小于它的根节点的值#xff0c;右子树上所有节点的值均大于它的根节点的值#xff1b;利用该性质#xff0c;可以实现二叉搜索树特有的自顶向下遍历 700. 二叉搜索树中的搜索 思路1、自顶向下的遍… 二叉搜索树是一个有序树每个二叉树都满足左子树上所有节点的值均小于它的根节点的值右子树上所有节点的值均大于它的根节点的值利用该性质可以实现二叉搜索树特有的自顶向下遍历 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
