938. 二叉搜索树的范围和
思路: 明确二叉搜索树的性质。按中序遍历后得到的数组是升序排列的。
L和R中间的数其实也相当于[L, R]之间的数。这样有几种方法可以得到:
注意: root = [10, 5, 15, 3, 7, 13, 18, 1, null, 6]
是按层从左到右给出的。
方法一、直接遍历二叉树,遍历过程中直接把[L, R]之间的数相加。
遍历条件: if node.val < R:
stack.append(node.right)
if node.val > L:
stack.append(node.left)
# 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, L, R):
"""
:type root: TreeNode
:type L: int
:type R: int
:rtype: int
"""
res, stack = 0, [root]
while stack:
node = stack.pop()
if node: # 只考虑不为空的节点
if L<=node.val<=R:
res += node.val
if node.val < R:
stack.append(node.right)
if node.val > L:
stack.append(node.left)
return res
方法二、中序遍历后得到有序数组,再次遍历得到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, L, R):
"""
:type root: TreeNode
:type L: int
:type R: int
:rtype: int
"""
global result
result = []
res = self.inorder(root)
left = right = 0
for i, val in enumerate(res):
if val == L:
left = i
elif val == R:
right = i
break
return sum(res[left:right+1])
def inorder(self, root):
if root is None:
return
self.inorder(root.left)
result.append(root.val)
self.inorder(root.right)
return result
中间参考了:https://blog.****.net/qq_17550379/article/details/84034131