首页 > 编程语言 >代码随想录算法训练营第二十天|leetcode235. 二叉搜索树的最近公共祖先、leetcode701.二叉搜索树中的插入操作、leetcode450.删除二叉搜索树中的节点

代码随想录算法训练营第二十天|leetcode235. 二叉搜索树的最近公共祖先、leetcode701.二叉搜索树中的插入操作、leetcode450.删除二叉搜索树中的节点

时间:2024-11-08 10:59:25浏览次数:1  
标签:None right val root self 二叉 搜索 树中 left

1 leetcode235. 二叉搜索树的最近公共祖先

题目链接:235. 二叉搜索树的最近公共祖先 - 力扣(LeetCode)

文章链接:代码随想录

视频链接:二叉搜索树找祖先就有点不一样了!| 235. 二叉搜索树的最近公共祖先_哔哩哔哩_bilibili

思路:用之前一样的方法,哈哈哈哈哈,好处就是做出来了,但是我觉得需要优化;我觉得应该有一个就是左右走的方式会变,但是自己写还是不知道应该怎么输出

1.1 自己的思路

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if root ==None:
            return root
        if root==p or root==q:
            return root
        left = self.lowestCommonAncestor(root.left,p,q)
        right = self.lowestCommonAncestor(root.right,p,q)
        if left!=None and right!=None:
            return root
        if left==None and right !=None:
            return right
        if left!=None and right == None:
            return left
        if left==None and right == None:
            return None

1.2 看视频后的思路

1.2.1递归法的思路

emmm,怎么说呢,我会忘记值进行比较这回事,所以容易弄错,但是后来看了一下视频就会了

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if root ==None:
            return root
        if root.val<p.val and root.val<q.val:
            right = self.lowestCommonAncestor(root.right,p,q)
            if right !=None:
                return right
        if root.val>p.val and root.val>q.val:
            left = self.lowestCommonAncestor(root.left,p,q)
            if left!=None:
                return left
        return root        
1.2.2 迭代法的思路
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        while root:
            if root.val>p.val and root.val>q.val:
                root = root.left
            elif root.val<p.val and root.val<q.val:
                root = root.right
            else:
                return root

1.3 本题小结

  1. 朦胧美在这一刻体现出来了,做起来真顺手,但是当自己去尝试的时候就写不出来了,然后看了讲解,就会觉得非常明了,,,
  2. 真的没有什么难点,就是不敢尝试

2 leetcode701.二叉搜索树中的插入操作

题目链接:701. 二叉搜索树中的插入操作 - 力扣(LeetCode)

文章链接:代码随想录

视频链接:原来这么简单? | LeetCode:701.二叉搜索树中的插入操作_哔哩哔哩_bilibili

思路:如果目标值比根节点小,往左走,否则往右走;写了中间代码,不知道终止条件应该怎么写,难呀

2.1 自己的代码

真就把中间想到了,不会写前后,不可以运行,只能写这样的

		if root.val<val:
            self.insertIntoBST(root.right,val)
        if root.val>val:
            self.insertIntoBST(root.left,val)

2.2 视频后的思路

不是很懂得一道题目,但是呢还是做了一下子吧

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def __init__(self):
        self.parent =None
    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        parent = TreeNode(0)
        if root ==None:
            root = TreeNode(val)
        self.insert(root,val)
        return root
    def insert(self,root,val):
        if root == None:
            node = TreeNode(val)
            if val>self.parent.val:
                self.parent.right = node
            else:
                self.parent.left =node
            return
        self.parent = root
        if root.val<val:
            self.insert(root.right,val)
        if root.val>val:
            self.insert(root.left,val)        

2.3 本题小结

  1. 这道题,看的不是很明白,虽然跟着一起做完了,但是我真的不是很懂,二刷的时候再来写一遍吧

3 leetcode450.删除二叉搜索树中的节点

题目链接:450. 删除二叉搜索树中的节点 - 力扣(LeetCode)

文章链接:代码随想录

视频链接:调整二叉树的结构最难!| LeetCode:450.删除二叉搜索树中的节点_哔哩哔哩_bilibili

思路:还是定义两个值,然后找,找到了Node和key相等的时候,就将其放入一个空的链表中,然后让这个左子树放到当前节点的位置,或者右节点不断前移就好了

3.1 自己的代码

我的代码,就是说,这个值在里面是删除不了的,我想的是如果遇到了,就将当前节点替换成他的左节点的值,结果值不在的情况满足了,在的用不了,,,

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def __init__(self):
        self.parent = None
        self.delnum = None
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        if root==None:
            return
        self.deletenum(root,key)
        return root
    def deletenum(self,root,key):
        if root == None:
            if root== key:
                self.delnum = root
                root = root.left
            return
        if root.val >key:
            self.deletenum(root.right,key)
        if root.val <key:
            self.deletenum(root.left,key)

3.2 视频后的思路

这里最难的地方果然是左子树和右子树都不为空进行删除的时候,这里写错了一些,而且还很不理解,最后自己画了个图片,去做循环的这一块就理解了

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        if root == None:
            return root
        if root.val == key:
            if root.left==None and root.right ==None:
                return None
            elif root.left==None and root.right!=None:
                return root.right
            elif root.left!=None and root.right == None:
                return root.left
            else:
                cur = root.right
                while cur.left:
                    cur = cur.left
                cur.left = root.left
                return root.right
        if key<root.val:
            root.left = self.deleteNode(root.left,key)
        if key>root.val:
            root.right = self.deleteNode(root.right,key)
        return root

3.3 本题小结

  1. 这种题首先要分清楚情况,删除的有五种情况
    1. 这个数据不在里面
    2. 在里面但是左右子树都为空
    3. 左为空右不为空
    4. 左不为空右为空
    5. 左右都不为空的情况
  2. 对于这类题,感觉还是要想清楚了再下手吧,很容易没想清楚

4 今日小结

  1. 第一道题可以根据之前的那个题目的思路来做,但是因为是搜索树,所以满足条件就是左子树的值永远比根节点小,右子树的值永远比根节点大的特点去写,就好了
  2. 第二道题,卡了一下但是今儿再去看解题的时候其实思路挺明确的,就是先将其赋值到最底层的那个数值,然后进行一个插入的操作,不断返回
  3. 第三题,难点就是左右子树都不为空,如何删除节点,最后画了个图去尝试了一下,就明白了,果然编程题和本子是最搭配的

标签:None,right,val,root,self,二叉,搜索,树中,left
From: https://www.cnblogs.com/csfy0524/p/18534680

相关文章

  • 二叉树的递归遍历和迭代遍历
    递归每次写递归,都按照这三要素来写,可以保证大家写出正确的递归算法!确定递归函数的参数和返回值:确定哪些参数是递归的过程中需要处理的,那么就在递归函数里加上这个参数,并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。确定终止条件:写完了递归算法,运行的时......
  • 洛谷题单指南-二叉堆与树状数组-P2827 [NOIP2016 提高组] 蚯蚓
    原题链接:https://www.luogu.com.cn/problem/P2827题意解读:初始n个数,每次取最大值x,根据u/v分成两部分:x*u/v,x-x*u/v,然后其余数都增加q,整个过程重复m次。输出有两类数据:第t,2t,3t...次取出的最大值;最后剩余的数第t,2t,3t...个,从大到小输出。解题思路:直观上,通过模拟法可以实......
  • 验证二叉搜索树
    题目描述给你一个二叉树的根节点root,判断其是否是一个有效的二叉搜索树。有效二叉搜索树定义如下:节点的左子树只包含小于当前节点的数。节点的右子树只包含大于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。98.验证二叉搜索树-力扣(LeetCode) 解题思......
  • 大语言模型是搜索匹配还是智能生成?
    随着人工智能技术的迅猛发展,尤其是大语言模型(如GPT-3、GPT-4等)的问世,许多人开始讨论这些模型到底是依靠“搜索匹配”还是“智能生成”来回答问题、生成文本。这个问题关系到大语言模型的本质及其应用前景,对AI的认知和使用也有深远影响。在辩论这一话题时,我们可以从以下几个方......
  • 路径分析算法—基于A*算法的路径搜索
    原文链接:路径分析算法—基于A*算法的路径搜索–每天进步一点点A*算法擅长解决静态路径中最短路径问题,而又不同于Dijkstra算法和Floyd算法,该算法综合了广度优先搜索(BreadthFirstSearch)和Dijkstra算法的优点:在进行启发式搜索提高算法效率的同时,可以保证找到一条最优路径(基于评......
  • Java深度优先搜索(DFS)算法实现
    标题:Java深度优先搜索(DFS)算法实现引言:深度优先搜索(Depth-FirstSearch,DFS)是一种常用的图遍历算法,它通过递归地遍历图中的每个顶点,来寻找特定的路径或解决某些问题。本篇博客将介绍如何用Java语言实现深度优先搜索算法。算法思想:深度优先搜索算法的基本思想是先访问一个......
  • AI 搜索来势汹汹,互联网将被颠覆还是进化?
    最近,美国新闻集团起诉了知名AI搜索引擎PerplexityAI。也许你会想,这不就是又一起“AI惹官司”吗?其实,这次情况不太一样,甚至可能会改变我们未来上网的方式!争议的焦点是什么?是未来的AI搜索——即那些能从全网总结信息的“AI答题王”。这些AI不只是简单的聊天机器人,而是能......
  • 基于信息增益和基尼指数的二叉决策树
    #coding:UTF-8'''基于信息增益和基尼指数的二叉决策树的实现。该决策树可以用于分类问题,通过选择合适的特征来划分样本。'''fromcollectionsimportCounterclassbiTree_node:'''二叉树节点定义每个节点可以是叶子节点或内部节点。'''def_......
  • 华为OD机试真题-数组二叉树码-2024年OD统一考试(E卷)
    最新华为OD机试考点合集:华为OD机试2024年真题题库(E卷+D卷+C卷)_华为od机试题库-CSDN博客     每一题都含有详细的解题思路和代码注释,精编c++、JAVA、Python三种语言解法。帮助每一位考生轻松、高效刷题。订阅后永久可看,发现新题及时跟新。题目描述二叉树也可以用数组来......
  • 数据结构 ——— 链式二叉树oj题:相同的树
    目录题目要求手搓两个链式二叉树代码实现 题目要求给你两棵二叉树的根节点 p 和 q ,编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。手搓两个链式二叉树代码演示://数据类型typedefintBTDataType;......