跟随carl代码随想录刷题
语言：python

---

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

题目：给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数，其数值等于两值之差的绝对值。

题目分析

遇到在二叉树上求最值、差值之类的，就把它想成在有序数组上求最值，求差值，这样就简单多了！

1. 将二叉树转换成有序数组
2. 遍历数组，求最小差值

⭐️初始化最小值的代码：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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

迭代法——中序遍历

# 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

迭代法——中序遍历——指针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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

手画遍历过程：

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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

迭代法——指针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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

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)  # 左
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27