一、501. 二叉搜索树中的众数

1.1、题目描述

1.2、题解

1.2.1、中序遍历 结果升序

# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def __init__(self) -> None: self.pre = -1 self.count = 0 # target[0] 记录最大的记录数， target[1:] 记录众数元素 self.target = [0, 0] def findMode(self, root: TreeNode) -> List[int]: if not root: return [] self.inorderTraversal(root) print(self.target, self.pre, self.count) # 最后的数没有对比， if self.count > self.target[0]: self.target = [self.count, self.pre] elif self.count == self.target[0]: self.target.append(self.pre) return self.target[1:] # 中序遍历: 先遍历左子树， 再遍历根节点， 最后遍历右子树 def inorderTraversal(self, root: TreeNode) -> None: if not root: return None # 左子树 if root.left: self.inorderTraversal(root.left) # 根节点 if self.pre == -1: self.pre = root.val self.count = 1 elif self.pre == root.val: self.count += 1 else: if self.count > self.target[0]: # 更新众数 self.target = [self.count, self.pre] elif self.count == self.target[0]: # 众数有多个, 追加众数 self.target.append(self.pre) self.pre = root.val self.count = 1 # 右子树 if root.right: self.inorderTraversal(root.right)

二、530. 二叉搜索树的最小绝对差

# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def __init__(self) -> None: self.min = float('inf') self.pre = -1 def getMinimumDifference(self, root: TreeNode) -> int: self.inorderTraversal(root) return self.min # 中序遍历: 先遍历左子树， 再遍历根节点， 最后遍历右子树 def inorderTraversal(self, root: TreeNode) -> None: # 左子树 if root.left: self.inorderTraversal(root.left) # 根节点 if self.pre != -1: self.min = min(self.min, abs(self.pre - root.val)) self.pre = root.val # 右子树 if root.right: self.inorderTraversal(root.right)