Leetcode 938. 二叉搜索树的范围和
题目描述
给定二叉搜索树的根结点 root，返回 L 和 R（含）之间的所有结点的值的和。
二叉搜索树保证具有唯一的值。
示例 1:
输入：root = [10,5,15,3,7,null,18], L = 7, R = 15
输出：32
示例 2:
输入：root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10
输出：23
解法
使用有序二叉树的中序遍历可以拿到结果，不过可能存在较多无效的节点遍历。以 rangeSumBST(node,L,R) 函数表示 node 为根节点的二叉树在 [L,R] 之间的范围和，对于节点 node，存在以下三种情况：
- 若 node 节点值处于 [L,R] 之间，则结果 ret=node.val + rangeSumBST(node.left,L,R) + rangeSumBST(node.right,L,R)
- 若 node.val<L，则结果 ret=rangeSumBST(node.right,L,R)
- 若 node.val>L，则结果 ret=rangeSumBST(node.left,L,R)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def rangeSumBST(self, root: TreeNode, L: int, R: int) -> int:
if not root:
return 0
if root.val<L:
return self.rangeSumBST(root.right,L,R)
if root.val>R:
return self.rangeSumBST(root.left,L,R)
return root.val+self.rangeSumBST(root.left,L,R)+self.rangeSumBST(root.right,L,R)本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019.05.28 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读