Leetcode-938 Range Sum of BST

Description

题目描述

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

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

Example 1:

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

Example 2:

1
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 都在左子树中,递归查找左子树

    1
    2
    if root.val > R:
    // recursive
  2. 若根节点的值小于 L,则 L 和 R 都在右子树中,递归查找右子树

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

程序设计

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

1
2
3
4
5
6
7
8
9
10
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)

本文标题:Leetcode-938 Range Sum of BST

文章作者:Syncher

发布时间:2019年08月20日 - 21:08

最后更新:2019年10月10日 - 18:10

原始链接:https://0x400.com/2019-08-20-lc-938-range-sum-of-bst.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。