学习资料:https://programmercarl.com/0530.二叉搜索树的最小绝对差.html
530.二叉搜索树的最小绝对差(双指针法,pre&cur,设置最小差值初始为无穷大,当差值<最小差值就更新最小差值)
点击查看代码
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):def __init__(self):self.result = float('inf') # 设置最小值的初值为无穷大self.pre = Nonedef getMinimumDifference(self, root):""":type root: TreeNode:rtype: int"""if root is None:returnself.getMinimumDifference(root.left)# 因为中序遍历,这里root.val肯定大于self.pre.valif self.pre is not None:self.result = min(self.result, root.val-self.pre.val) self.pre = rootself.getMinimumDifference(root.right)return self.result
501.二叉搜索树中的众数(加两个函数,init & searchBST;双指针,当pre.val==cur.val,count+=1)
点击查看代码
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):def __init__(self):self.result = []self.pre = Noneself.count = 0self.maxCount = 0def searchBST(self, cur):if cur is None:returnself.searchBST(cur.left)if self.pre is None:self.count = 1elif self.pre.val == cur.val:self.count += 1else:self.count = 1self.pre = curif self.count == self.maxCount:self.result.append(cur.val)if self.count > self.maxCount:self.maxCount = self.countself.result = [cur.val]self.searchBST(cur.right)returndef findMode(self, root):""":type root: TreeNode:rtype: List[int]"""self.count = 0self.maxCount = 0self.pre = Noneself.result = []self.searchBST(root)return self.result
236.二叉树的最近公共祖先(看代码简单,但是想不通;递归;左右中:后序遍历)
点击查看代码
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Solution(object):def lowestCommonAncestor(self, root, p, q):""":type root: TreeNode:type p: TreeNode:type q: TreeNode:rtype: TreeNode"""if root == q or root == p or root is None:return rootleft = self.lowestCommonAncestor(root.left, p, q)right = self.lowestCommonAncestor(root.right, p, q)if left is not None and right is not None:return rootif left is None and right is not None:return rightelif left is not None and right is None:return leftelse:return None
PS:今天的后两道题没看懂,先抄一下
延迟了一天,因为昨晚有今年最大的月亮又恰逢难得的晴天,看到了月球超级靓但是还是差点意思没看到凹,不过第一次看到土星,好远好小好棒,还有环,就是没注意颜色
昨天还吃了美味寿司,一个人干了两大碟,有实力儿
破公司的秋招,把人当猴耍