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 本题小结
- 朦胧美在这一刻体现出来了,做起来真顺手,但是当自己去尝试的时候就写不出来了,然后看了讲解,就会觉得非常明了,,,
- 真的没有什么难点,就是不敢尝试
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 本题小结
- 这道题,看的不是很明白,虽然跟着一起做完了,但是我真的不是很懂,二刷的时候再来写一遍吧
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 本题小结
- 这种题首先要分清楚情况,删除的有五种情况
- 这个数据不在里面
- 在里面但是左右子树都为空
- 左为空右不为空
- 左不为空右为空
- 左右都不为空的情况
- 对于这类题,感觉还是要想清楚了再下手吧,很容易没想清楚
4 今日小结
- 第一道题可以根据之前的那个题目的思路来做,但是因为是搜索树,所以满足条件就是左子树的值永远比根节点小,右子树的值永远比根节点大的特点去写,就好了
- 第二道题,卡了一下但是今儿再去看解题的时候其实思路挺明确的,就是先将其赋值到最底层的那个数值,然后进行一个插入的操作,不断返回
- 第三题,难点就是左右子树都不为空,如何删除节点,最后画了个图去尝试了一下,就明白了,果然编程题和本子是最搭配的