Leetcode-938 Range Sum of BST

Description

题目描述

https://leetcode.com/problems/range-sum-of-bst/

给定一颗二叉搜索树，返回节点的值在 L 和 R 之间的所有节点（包括 L 和 R）的和，其中二叉搜索树的所有节点的值唯一。r如下案例：

Example 1:

Input: root = [10,5,15,3,7,null,18], L = 7, R = 15
Output: 32

Example 2:

Input: root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10
Output: 23

分析

二叉搜索树（Binary Search Tree）是一颗空树或者具有如下性质的二叉树：

1. 若任意节点的左子树不空，则左子树所有节点的值均小于他的根节点的值
2. 若任意节点的右子树不空，则右子树所有节点的值均大于他的根节点的值
3. 任意节点的左、右子树也分别是二叉搜索树
4. 没有键值相等的节点

根据二叉搜索树的特点，假设 L 小于 R，我们按照如下规则查找 L 和 R：

1. 若根节点的值大于 R，则 L 和 R 都在左子树中，递归查找左子树

   if root.val > R:
       // recursive

2. 若根节点的值小于 L，则 L 和 R 都在右子树中，递归查找右子树

3. 否则说明根节点在 R 和 L 中间，累加根节点的值，分别往左右两边查找 L 和 R，直到 L 和 R 都被找到，查找的过程中，累加在 R 和 L 中间的节点的值

程序设计

根据如上分析，写出如下代码

class Solution:
    def rangeSumBST(self, root: TreeNode, L: int, R: int) -> int:
        if not root:
            return 0
        if root.val > R:
            return self.rangeSumBST(root.left, L, R)
        if root.val < L:
            return self.rangeSumBST(root.right, L, R)

        return root.val + self.rangeSumBST(root.left, L, R) + self.rangeSumBST(root.right, L, R)