代码随想录算法训练营第十八天| 530、二叉搜索树的最小绝对差 501、二叉搜索树中的众数 236、二叉树的最近公共祖先

目录530. 二叉搜索树的最小绝对差题目描述解题思路501. 二叉搜索树中的众数题目描述解题思路236. 二叉树的最近公共祖先题目描述解题思路530. 二叉搜索树的最小绝对差题目描述给你一个二叉搜索树的根节点root返回树中任意两不同节点值之间的最小差值。差值是一个正数其数值等于两值之差的绝对值。解题思路二叉搜索树和中序遍历是好朋友找到二叉搜索树的最小绝对差就是找其对应的中序遍历的两数之间最小差值暴力解法是将二叉搜索树转变为中序数组存储起来再在中序数组中循环找最小差值也可以通过记录二叉树当前遍历的前一个数据计算最小绝对差8 | | 4 10 | | | 1 7 15 大概就是cur遍历14781015 pre遍历 147810class Solution: def getMinimumDifference(self, root: Optional[TreeNode]) - int: self.pre None self.res float(inf) self.travesal(root) return self.res def travesal(self,cur): if not cur:return self.travesal(cur.left) #pre为空cur指向中序遍历第一个数 if self.pre: self.res min(self.res,cur.val - self.pre.val) #将pre赋予cur值cur再指向下一个数 self.pre cur self.travesal(cur.right)501. 二叉搜索树中的众数题目描述给你一个含重复值的二叉搜索树BST的根节点root找出并返回 BST 中的所有 众数即出现频率最高的元素。如果树中有不止一个众数可以按任意顺序返回。假定 BST 满足如下定义结点左子树中所含节点的值小于等于当前节点的值结点右子树中所含节点的值大于等于当前节点的值左子树和右子树都是二叉搜索树解题思路二叉搜索树和中序遍历是好朋友由于中序遍历数组有序所以用双指针直接维护当前最大频率class Solution: def __init__(self): self.result [] self.pre None self.count 1 self.MaxCount float(-inf) def findMode(self, root: Optional[TreeNode]) - List[int]: self.travesal(root) return self.result def travesal(self,cur): #中序遍历 if not cur:return self.travesal(cur.left) #1.cur指向第一个节点 if not self.pre: self.count 1 #2.pre节点的值和cur节点值相同 elif self.pre.val cur.val: self.count 1 #3.pre节点存在且值与cur不同 else: self.count 1 #4.将pre节点指向下一个节点当前节点 self.pre cur #5.count为当前统计最大频率 if self.count self.MaxCount: self.result.append(cur.val) #6.count比当前最大频率更大更新最大频率并清空非最大频率的元素重新添加最大频率的元素 if self.count self.MaxCount: self.result.clear() self.MaxCount self.count self.result.append(cur.val) self.travesal(cur.right)236. 二叉树的最近公共祖先题目描述给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为“对于有根树 T 的两个节点 p、q最近公共祖先表示为一个节点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。”解题思路三部曲遍历方式后序遍历先看左右子树是否含有指定节点依据条件返回节点参数根节点指定节点递归终止条件当前节点为空时返回node节点模拟过程另一种情况就是节点为他自己的祖先由于指定节点一定在二叉树中所以若找到一个节点但是另一颗子树没有该节点出现那么此时这个节点就是祖先节点另一个指定节点在该节点的下方遍历时不会遍历到class Solution: def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) - TreeNode: return self.travesal(root,p,q) def travesal(self,node,p,q): #如果当前节点为空说明没有找到pq if not node:return node #如果当前节点就是pq直接返回当前节点 if p node or q node:return node #如果没有左右子树中寻找 left self.travesal(node.left,p,q) right self.travesal(node.right,p,q) #当前节点就是最近祖先一直返回公共祖先 if left and right:return node #答案在左边 if left and not right:return left #答案在右边 if not left and right:return right