題目描述

給定二叉搜索樹的根結(jié)點 root，返回 L 和 R（含）之間的所有結(jié)點的值的和。

二叉搜索樹保證具有唯一的值。

示例 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

解法

使用有序二叉樹的中序遍歷可以拿到結(jié)果，不過可能存在較多無效的節(jié)點遍歷。以 rangeSumBST(node,L,R) 函數(shù)表示 node 為根節(jié)點的二叉樹在 [L,R] 之間的范圍和，對于節(jié)點 node，存在以下三種情況：

• 若 node 節(jié)點值處于 [L,R] 之間，則結(jié)果 ret=node.val + rangeSumBST(node.left,L,R) + rangeSumBST(node.right,L,R)

• 若 node.val<L，則結(jié)果 ret=rangeSumBST(node.right,L,R)

• 若 node.val>L，則結(jié)果 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)