[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:

Range Sum of BST - LeetCode

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.