Leetcode 第二十天 2024.8.6

1. ：二叉搜索树的最小绝对差
 题目链接: 530. 二叉搜索树的最小绝对差 - 力扣（LeetCode）
应用条件：递归，中序遍历

难点：

和验证二叉搜索数一样，遍历整个二叉搜索数，即可遍历出结果。

个人错误：

思路：

# 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.pre = Noneself.res = float(inf)def getMinimumDifference(self, root: Optional[TreeNode]) -> int:if not root:returnself.getMinimumDifference(root.left)if self.pre != None:ca = root.val - self.pre.valself.res = min(self.res,ca)self.pre = rootself.getMinimumDifference(root.right)return self.res

2. ：二叉搜索树中的众数
 题目链接: 501. 二叉搜索树中的众数 - 力扣（LeetCode）
应用条件：递归，中序遍历

难点：

这道题也是同样用上一道题的思路可以解答，遍历整个二叉树，然后将出现的值以及出现次数记录到字典中，最后在对字典进行排序。

个人错误：

又忘了怎么对字典的value排序，根据字典中的value对key进行排序用sortdic = sorted(findic.items(), key= lambda item:item[1],reverse = True)，注意其中的key= lambda item:item[1]不能省略，省略会自动按照key进行排序

思路：

# 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.res = {}def findMode(self, root: Optional[TreeNode]) -> List[int]:findic = self.trav(root)sortdic = sorted(findic.items(), key= lambda item:item[1],reverse = True)ma = sortdic[0][1]finres = []for item in sortdic:if item[1] == ma:finres.append(item[0])return finresdef trav(self,root):if not root:returnself.trav(root.left)if root.val in self.res:self.res[root.val] += 1else:self.res[root.val] = 1self.trav(root.right)return self.res

3. ：二叉树的最近公共祖先
 题目链接: 236. 二叉树的最近公共祖先 - 力扣（LeetCode）
应用条件：后序遍历，递归

难点：

本题要想到是从底部往顶部遍历二叉树，要对二叉树底层判断是不是存在p，q，然后如果存在则返回他们的公共祖先，从底部往顶部遍历的情况优先考虑后序遍历。

个人错误：

同时这里要有参数来接住返回值的，从而再继续用这个参数向上传递，直到遍历完整个数

思路：

# 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 rootif root == p or root == q:return rootleft = self.lowestCommonAncestor(root.left,p,q)right = self.lowestCommonAncestor(root.right,p,q)if left == None and right == None:return Noneelif left!= None and right == None:return leftelif right!= None and left == None:return rightelse:return root