day16-数据结构力扣

530.二叉搜索树的最小绝对差题目链接530. 二叉搜索树的最小绝对差 - 力扣LeetCode思路看到题我想到的是先中序遍历得到结果数组因为二叉搜索树遍历得到的数组是有序的我对前后元素求差值存放到一个数组然后再求这个数组的最小值试一下可以提交# 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 getMinimumDifference(self, root: Optional[TreeNode]) - int: if not root: return 0 resself.traversal(root) print(res) minus[] for i in range(len(res)-1): minus.append(res[i1]-res[i]) return min(minus) def traversal(self,root: Optional[TreeNode])-List: if not root: return [] return self.traversal(root.left)[root.val]self.traversal(root.right)501.二叉搜索树中的众数题目链接501. 二叉搜索树中的众数 - 力扣LeetCode思路其实比较简单的思路时间复杂度可能更高但是我现在只求能过提交通过我把二叉搜索树这种可以遍历得到数组然后再进行处理的都这么解决先遍历得到数组统计每个数出现的次数返回出现次数最多的数。但是这里有一个难点就是需要把数字和出现的次数对应记录(字典)然后不是返回次数最多的次数而是这个次数对应的数字提交# 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 findMode(self, root: Optional[TreeNode]) - List[int]: if not root: return [] numsself.traversal(root) count{} for num in nums: count[num]count.get(num,0)1 max_numNone max_cnt0 res[] for num,cnt in count.items(): if cntmax_cnt: max_cntcnt for num,cnt in count.items(): if max_cntcnt: res.append(num) return res def traversal(self,root): if not root: return [] return self.traversal(root.left)[root.val]self.traversal(root.right)236. 二叉树的最近公共祖先题目链接236. 二叉树的最近公共祖先 - 力扣LeetCode思路题的意思是大概能看懂自己看图大概也知道是什么。但是判断依据不知道怎么写。p,q这两个节点从底往上遍历交汇的最近的节点就是他们的最近公共祖先从下往上后序遍历二叉树分别在左右子树里找 p 和 q如果左右都找到了说明当前节点就是最近公共祖先如果只在一边找到就把那边的结果往上返回遇到空节点、p 或 q 就直接返回。提交# 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 rootq or rootp or root is None: return root leftself.lowestCommonAncestor(root.left,p,q) rightself.lowestCommonAncestor(root.right,p,q) if left is not None and right is not None: return root if left is None and right is not None: return right elif left is not None and right is None: return left else: return None