文章目录
跟随carl代码随想录刷题
语言：python
530. 二叉搜索树的最小绝对差
题目：给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数，其数值等于两值之差的绝对值。
题目分析
遇到在二叉树上求最值、差值之类的，就把它想成在有序数组上求最值，求差值，这样就简单多了！
- 将二叉树转换成有序数组
- 遍历数组，求最小差值
⭐️初始化最小值的代码：r = float("inf")设f是一个无限大的数。
⭐️有序数组进行值比较的代码：for i in range(len(result)-1): r = min(abs(result[i+1]-result[i]), r)
完整代码如下
递归法
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
# 递归法
result = []
r = float("inf") # 设f是一个无限大的数
def traversal(root):
if not root:
return
traversal(root.left)
result.append(root.val)
traversal(root.right)
traversal(root)
for i in range(len(result)-1):
r = min(abs(result[i+1]-result[i]), r)
return r
迭代法——中序遍历
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
# 递归法
result = []
r = float("inf") # 设f是一个无限大的数
st = []
if root:
st.append(root)
while st:
cur = st.pop()
if cur:
if cur.right:
st.append(cur.right)
st.append(cur)
st.append(None)
if cur.left:
st.append(cur.left)
else:
cur = st.pop()
result.append(cur.val)
for i in range(len(result)-1):
r = min(abs(result[i+1]-result[i]), r)
return r
迭代法——中序遍历——指针pre
图中数字表示第n次遍历：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
stack = []
cur = root
pre = None
result = float('inf')
while cur or stack:
if cur:
stack.append(cur)
cur = cur.left
else:
cur = stack.pop()
if pre:
result = min(result, cur.val - pre.val)
pre = cur
cur = cur.right
return result
手画遍历过程：
501. 二叉搜索树中的众数
题目：给你一个
含重复值的二叉搜索树（BST）的根节点 root，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
如果树中有不止一个众数，可以按 任意顺序 返回。
.
假定 BST 满足如下定义：
结点左子树中所含节点的值 小于等于 当前节点的值
结点右子树中所含节点的值 大于等于 当前节点的值
左子树和右子树都是二叉搜索树
题目分析
指针pre
数组的众数怎么求？
完整代码如下
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def __init__(self):
self.pre = TreeNode()
self.result = []
self.max_count = 0 # 用于统计中枢的变量，提前初始化为0
self.count = 0
def findMode(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return root
self.search_BST(root)
return self.result
def search_BST(self, cur)-> None:
if not cur:
return None
self.search_BST(cur.left)
# 第一个节点
if not self.pre: # 如果与第一个节点的值不同
self.count = 1
elif self.pre.val == cur.val: # 如果与第一个节点的值相同
self.count += 1
else: # 如果与第一个节点的值不同
self.count = 1
self.pre = cur
if self.count == self.max_count:
self.result.append(cur.val)
if self.count > self.max_count:
self.max_count = self.count
self.result = [cur.val] # 清空self.result，确保result之前的的元素都失效
self.search_BST(cur.right)
迭代法——指针pre
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def findMode(self, root: Optional[TreeNode]) -> List[int]:
stack = []
cur = root
pre = None
maxCount, count = 0, 0 # 最大频率、频率
res = []
while cur or stack:
if cur: # 指针访问节点，直至底层
stack.append(cur) # 将节点放入栈中
cur = cur.left # 左
else:
cur = stack.pop() # 中
if pre == None: # 第一个节点
count = 1
elif pre.val == cur.val: # 与前一个节点数值相同
count += 1
else:
count = 1 # 与前一个节点数值不同
if count == maxCount: # 如果和最大值相同，就放进result数组中
res.append(cur.val)
if count > maxCount: # 如果计数大于最大值频率
maxCount = count # 更新最大频率
res.clear() # 关键一步：清空result
res.append(cur.val)
pre = cur
cur = cur.right # 右
return res
538. 把二叉搜索树转换为累加树
题目：给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下，二叉搜索树满足下列约束条件：
节点的左子树仅包含键 小于 节点键的节点。
节点的右子树仅包含键 大于 节点键的节点。
左右子树也必须是二叉搜索树。
👉示例1：
输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
👉示例 2：
输入：root = [0,null,1]
输出：[1,null,1]
👉示例 3：
输入：root = [1,0,2]
输出：[3,3,2]
题目分析
本题与1038. 从二叉搜索树到更大和树一模一样，只是题目中称呼不同：累加树、更大的树。
carl的总结：
涉及到二叉树的
构造，无论普通二叉树还是二叉搜索树一定前序，都是先构造中节点。求普通二叉树的
属性，一般是后序，一般要通过递归函数的返回值做计算。不过普通二叉树属性的题目具体使用前序、中序还是后序，需要具体问题具体分析。求二叉
搜索树的属性，一定是中序了，要不白瞎了有序性了。
完整代码如下
递归法——指针pre
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def __init__(self):
self.pre = TreeNode()
def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
"""
倒序累加替换
[2, 5, 13] -> [[2]+[1]+[0], [2]+[1], [2]] -> [20, 18, 13]
"""
self.traversal(root)
return root
def traversal(self, root):
if not root: # 因为要遍历整棵树，所以没有返回值
return None
# 单层递归逻辑：中序遍历的反译：右中左
self.traversal(root.right) # 右
# 中节点：用当前root的值加上pre的值
root.val += self.pre.val
self.pre = root
self.traversal(root.left) # 左