[英雄星球七月集训LeetCode解题日报] 第20日 BST

日报

• 今天两道题。

题目

一、 938. 二叉搜索树的范围和

链接: 938. 二叉搜索树的范围和

1. 题目描述

2. 思路分析

• 由于是BST，因此我们可以判断root.val的范围选择向左或向右递归。
• 如果val的范围介于[low,high]里，那么两边都要计算。

3. 代码实现

class Solution:
    def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:
        if not root:
            return 0
        if root.val<low:
            return self.rangeSumBST(root.right,low,high) 
        if root.val > high:
            return self.rangeSumBST(root.left,low,high)
        
        return root.val + self.rangeSumBST(root.right,low,high) + self.rangeSumBST(root.left,low,high)
1
2
3
4
5
6
7
8
9
10

二、 剑指 Offer II 054. 所有大于等于节点的值之和

链接: 剑指 Offer II 054. 所有大于等于节点的值之和

1. 题目描述

2. 思路分析

• 想了好一会，甚至看了眼数据范围想遍历下来排序然后二分前缀和了。
• 在这个基础上想了下这是BST是有序的，按中根遍历可以省去排序；想了一下，能倒序遍历不就直接累加就行了吗。
• 于是发现只需要按右根左的顺序遍历累加即可。

3. 代码实现

class Solution:
    def convertBST(self, root: TreeNode) -> TreeNode:
        s = 0
        def dfs(root):
            if not root:
                return 
            nonlocal s
            dfs(root.right)
            s += root.val 
            root.val = s
            dfs(root.left)
        dfs(root)
        return root
1
2
3
4
5
6
7
8
9
10
11
12
13

三、 538. 把二叉搜索树转换为累加树

链接: 538. 把二叉搜索树转换为累加树

1. 题目描述

同上题。

四、1038. 从二叉搜索树到更大和树

链接: 1038. 从二叉搜索树到更大和树

1. 题目描述

同上题。