[LeetCode]#938. Range Sum of BST

Environment: Python 3.7

Key technique: treenode, .pop

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

Analysis:

1. Use treeNode class to create tree Node structure
2. We can find the search is 7–5–10–15.
3. L=7, R=15 and the answer is 10+7+15=32

Solution:

1. TreeNode class
class Node:def __init__(self, val):self.left = None
self.right = None
self.val = val
def insert(self, val):if self.val:
if val < self.val:
if self.left is None:
self.left = Node(val)
else:
self.left.insert(val)
elif val > self.val:
if self.right is None:
self.right = Node(val)
else:
self.right.insert(val)
else:
self.val = val
def PrintTree(self):
if self.left:
self.left.PrintTree()
print( self.val),
if self.right:
self.right.PrintTree()

2. How to use?

root=Node(10)
root.insert(5)
root.insert(15)
root.insert(3)
root.insert(7)
root.insert(18)
root.PrintTree() #check tree

3.Sum of BST.

class Solution(object):
def rangeSumBST(self, root, L, R):
ans = 0
stack = [root]
while stack:
node = stack.pop()
if node:
if L <= node.val <= R:
ans += node.val
if L < node.val:
stack.append(node.left)
if node.val < R:
stack.append(node.right)
return ans

Submissions:

Reference:

https://www.tutorialspoint.com/python_data_structure/python_binary_tree.htm

This is my first time to learn tree structure and it is very difficult to me.