題目描述
Given the root node of a binary search tree, return the sum of values of all nodes with value between L and R (inclusive).
The binary search tree is guaranteed to have unique values.
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
Note:
The number of nodes in the tree is at most 10000.
The final answer is guaranteed to be less than 2^31.
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class
Solution
(
object
)
:
def
rangeSumBST
(
self
,
root
,
L
,
R
)
:
"""
:type root: TreeNode
:type L: int
:type R: int
:rtype: int
"""
if
not
root
:
return
0
res
=
0
if
L
<=
root
.
val
<=
R
:
res
+=
root
.
val
res
+=
self
.
rangeSumBST
(
root
.
left
,
L
,
R
)
res
+=
self
.
rangeSumBST
(
root
.
right
,
L
,
R
)
elif
root
.
val
<
L
:
res
+=
self
.
rangeSumBST
(
root
.
right
,
L
,
R
)
elif
root
.
val
>
R
:
res
+=
self
.
rangeSumBST
(
root
.
left
,
L
,
R
)
return
res
簡化代碼：直接判斷尋找的方向。如果root節點小于R，說明右邊可以繼續搜索；如果root節點大于L，說明左邊可以繼續搜索。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class
Solution
(
object
)
:
def
rangeSumBST
(
self
,
root
,
L
,
R
)
:
"""
:type root: TreeNode
:type L: int
:type R: int
:rtype: int
"""
res
=
[
0
]
self
.
dfs
(
root
,
L
,
R
,
res
)
return
res
[
0
]
def
dfs
(
self
,
root
,
L
,
R
,
res
)
:
if
not
root
:
return
if
L
<=
root
.
val
<=
R
:
res
[
0
]
+=
root
.
val
if
root
.
val
<
R
:
self
.
dfs
(
root
.
right
,
L
,
R
,
res
)
if
root
.
val
>
L
:
self
.
dfs
(
root
.
left
,
L
,
R
,
res
)
參考來源：https://blog.csdn.net/fuxuemingzhu/article/details/83961263
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
