做网站电脑开一天用多少钱,网店推广的重要性,成全视频免费观看在线看第7季电视剧,天津大型网站设计公司写在前边的话
235. 二叉搜索树的最近公共祖先
题目链接 力扣题目链接
题目难度 中等
看到题目的第一想法 看到题目的第一想法#xff0c;除了昨天做过的普通二叉树的最近祖先的解法利用回溯从底向上搜索#xff0c;我会想到使用迭代法#xff0c;但我好像不太会使用到二…写在前边的话
235. 二叉搜索树的最近公共祖先
题目链接 力扣题目链接
题目难度 中等
看到题目的第一想法 看到题目的第一想法除了昨天做过的普通二叉树的最近祖先的解法利用回溯从底向上搜索我会想到使用迭代法但我好像不太会使用到二叉树搜索树的特性我是选择的层序遍历。得转换下思维了。
python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val x
# self.left None
# self.right Noneclass Solution:def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) - TreeNode:if not root:return rootqueue collections.deque([root])while queue:n len(queue)for i in range(n):node queue.popleft()if min(p.val, q.val) node.val max(p.val, q.val):return nodeif node.left:queue.append(node.left)if node.right:queue.append(node.right)return None 看完代码随想录的总结
文章讲解 代码随想录文章讲解
视频讲解 代码随想录视频讲解
解题思路 1. 递归法由于没有中节点的逻辑所以前中后序都是可以的。 递归三步曲 1入参根节点pq返回值满足条件的二叉树节点。 2终止条件节点空返回空 3单次递归逻辑如果节点小于pq那么就向右子树遍历如果节点值大 于pq那么就向左子树遍历否则就返回当前节点。 2. 迭代法 从根节点开始遍历如果当前节点小于pq那么就向右子树搜索如果当前节点值大于pq那么就像左子树搜索否则返回当前节点。
代码编写
python
# 递归法
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val x
# self.left None
# self.right Noneclass Solution:def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) - TreeNode:if not root:return rootprint(root.val)if root.val p.val and root.val q.val:right_res self.lowestCommonAncestor(root.right, p, q)if right_res:return right_resif root.val p.val and root.val q.val:left_res self.lowestCommonAncestor(root.left, p, q)if left_res:return left_resreturn root#********************************************************************************# 迭代法
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val x
# self.left None
# self.right Noneclass Solution:def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) - TreeNode:cur rootwhile cur:if cur.val p.val and cur.val q.val:cur cur.rightelif cur.val p.val and cur.val q.val:cur cur.leftelse:return curreturn None
java
701.二叉搜索树中的插入操作
题目链接 力扣题目链接
题目难度 中等
看到题目的第一想法 看到题目的第一想法是想用迭代法在遍历节点的时候找到要插入的位置。 python
# 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 insertIntoBST(self, root: Optional[TreeNode], val: int) - Optional[TreeNode]:node TreeNode(val)if not root:return nodecur rootwhile True:if val cur.val:print(cur.val)if not cur.left: cur.left nodereturn rootelse:cur cur.leftif val cur.val:if not cur.right:node TreeNode(val)cur.right nodereturn rootelse:cur cur.right
看完代码随想录的总结
文章讲解 代码随想录文章讲解
视频讲解 代码随想录视频讲解
解题思路 1.递归法需要记录父节点方案一可以通过递归函数的返回值完成父子节点的赋值这种方法比较便利方案二另外也可以找到要插入父节点位置以后再判断是插入到左节点还是右节点 递归三步曲方案一 入参当前节点以及要比较的数值返回值要插入的节点。 终止条件节点空则返回要插入的节点。 单次递归逻辑赋值当前节点给父节点如果节点值大于要比较的值那么向左子树遍历如果当前节点值小于要比较的值那么向右子树遍历。注意这里返回值会赋值给左右子节点。 递归三步曲方案二 入参当前节点以及要比较的数值无返回值。 终止条件节点空即下层左节点或者右节点为空了这个时候由于递归函数没有返回值所以需要检查比较值是大于父节点还是小于父节点小于插入到左节点大于插入到右节点。 单次递归逻辑赋值当前节点给父节点如果节点值大于要比较的值那么向左子树遍历如果当前节点值小于要比较的值那么向右子树遍历。
代码编写
python
#方案一
# 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.parent Nonedef reversal(self, cur, val):if not cur:node TreeNode(val)return nodeif cur.val val:cur.left self.reversal(cur.left, val)else:cur.right self.reversal(cur.right, val)return cur # 注意这里要一层一层返回最终返回的就是根节点了def insertIntoBST(self, root: Optional[TreeNode], val: int) - Optional[TreeNode]:if not root:return TreeNode(val)cur rootreturn self.reversal(cur, val)#********************************************************************# 方案二
# 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.parent Nonedef reversal(self, cur, val):if not cur:node TreeNode(val)if self.parent.val val:self.parent.left nodeelse:self.parent.right nodereturnself.parent curif cur.val val:self.reversal(cur.left, val)else:self.reversal(cur.right, val)def insertIntoBST(self, root: Optional[TreeNode], val: int) - Optional[TreeNode]:if not root:return TreeNode(val)cur rootself.reversal(cur, val)return root# ***********************************************************************# 迭代法
# 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 insertIntoBST(self, root: Optional[TreeNode], val: int) - Optional[TreeNode]:node TreeNode(val)if not root:return TreeNode(val)cur rootwhile cur:parent curif cur.val val:cur cur.leftelse:cur cur.rightif parent.val val:parent.left nodeelse:parent.right nodereturn root
java
450.删除二叉搜索树中的节点
题目链接 力扣题目链接
题目难度 中等
看到题目的第一想法 没接触过看到就觉得有点难
看完代码随想录的总结
文章讲解 代码随想录文字讲解
视频讲解 代码随想录视频讲解
解题思路 1. 递归法关键单层递归中的情况梳理 递归三步曲 1入参根节点和要比较的值返回值删除节点以后要返回的节点用于上一层递归来赋值。 2终止条件有五种情况第一种节点空则返回空说明没找到要删除的节点第二种遍历到的要删除的节点此时左右节点均为空那么直接返回空第三种遍历到要删除的节点此时左节点不为空右节点为空那么直接返回左节点第四种情况遍历到要删除的节点此时左节点空右节点不为空那么直接返回右节点第五种遍历到要删除的节点了此时左右子节点都不为空此时需要把左子树放到右子树当中将删除节点的左子树头结点放到删除节点的右子树的最左面节点的左孩子上整个时候就成了左节点空右节点非空的情况返回右节点。 3单层递归逻辑遍历左子树遍历右子树如果不满足上边终止条件则返回当前节点。
代码编写
python
# 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 reversal(self, root, key):if not root:return rootif root.val key:if not root.left and not root.right:return Noneelif root.left and not root.right:return root.leftelif not root.left and root.right:return root.rightelse:cur root.rightwhile(cur.left):cur cur.leftcur.left root.leftreturn root.rightif root.val key:root.left self.reversal(root.left, key)else:root.right self.reversal(root.right, key)return rootdef deleteNode(self, root: Optional[TreeNode], key: int) - Optional[TreeNode]:return self.reversal(root, key)
java
今日总结 今天的题目也都是二叉搜索树的题目做二叉搜索树的题目还是要注意利用其特性。在删除和插入二叉树节点的时候使用递归可以利用返回值进行节点赋值的操作这样比较简单不用重复去判断条件。
