宿迁网站推广,长沙建网站公司,网站建设平台的分析,常州网站推广优化二叉搜索树的最小绝对差
关键信息#xff1a;二叉搜索树表明了树有序的#xff01;遇到在二叉搜索树上求什么最值啊#xff0c;差值之类的#xff0c;就把它想成在一个有序数组上求最值#xff0c;求差值 # Definition for a binary tree node.
# class TreeNode:
# …二叉搜索树的最小绝对差
关键信息二叉搜索树表明了树有序的遇到在二叉搜索树上求什么最值啊差值之类的就把它想成在一个有序数组上求最值求差值 # 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 stack []result []while root or stack:if root:stack.append(root)root root.leftelse:node stack.pop(-1)result.append(node.val)root node.rightif len(result) 2:return res result[1] - result[0]for i in range(2, len(result)):res min(res, result[i] - result[i - 1])return res# 使用递归来做def getMinimumDifference(self, root: Optional[TreeNode]) - int:result self.getMinimumDifference1(root)min_res result[1] - result[0]for i in range(2,len(result)):min_res min(min_res, result[i] - result[i -1])return min_resdef getMinimumDifference1(self, root: Optional[TreeNode]) - int:if not root:return []left self.getMinimumDifference1(root.left) # 左right self.getMinimumDifference1(root.right) # 右return left [root.val] right # 左加中加右
或者更加简洁一点的方法 501. 二叉搜索树中的众数
思路求众数首先先到的是HashMap也就是字典或者利用二叉搜索树是有序的特点存在字典中
# 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 __init__(self):self.dict_1 {}self.max float(-inf)def findMode(self, root: Optional[TreeNode]) - List[int]:self.findMode1(root)print(self.dict_1,self.max)result []for i,k in self.dict_1.items():if k self.max:result.append(i)return resultdef findMode1(self, root: Optional[TreeNode]):if not root:return if root.val in self.dict_1:self.dict_1[root.val] 1else:self.dict_1[root.val] 1if self.dict_1[root.val] self.max:self.max self.dict_1[root.val]self.findMode1(root.left)self.findMode1(root.right)
236. 二叉树的最近公共祖先
难点出于惯性的思维我们都是从上往下遍历的而这道题需要我们从下往上遍历的需要用到后续遍历然后节点进行回溯一步一步往上传递 # 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 root is None or root p or root q:return rootleft self.lowestCommonAncestor(root.left, p , q) # 左right self.lowestCommonAncestor(root.right, p , q) # 右# 中的处理逻辑根据左右的结果判断这个后续遍历就很重要了if left and right:return rootelif not left and right:return rightelif left and not right:return leftelse:return None #都没有出现p或q的情况的返回给上一层的内容
或者精简版
class Solution:def lowestCommonAncestor(self, root, p, q):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:return rightreturn left
, p, q)if left is not None and right is not None:return rootif left is None:return rightreturn left
