[PYTHON] Let Code Day4 starting from scratch "938. Range Sum of BST"

Overview

It seems that coding tests are conducted overseas in interviews with engineers, and in many cases, the main thing is to implement specific functions and classes according to the theme.

As a countermeasure, it seems that a site called Let Code will take measures.

A site that trains algorithmic power that can withstand coding tests that are often done in the home.

I think it's better to have the algorithm power of a human being, so I'll solve the problem irregularly and write down the method I thought at that time as a memo.

Leetcode

Basically, I would like to solve the easy acceptance in descending order.

Last time Leet Code Day3 starting from zero "1313. Decompress Run-Length Encoded List"

problem

938. Range Sum of BST

BST is a Binary search tree, that is, a binary search tree.

I think that some people do not know the concept of the tree or it is ambiguous, so to explain it briefly, the tree creates a hierarchical structure in which multiple child nodes hang under one "root" as shown below. It is one of the ideas of the data structure. A terminal node that has no children is called a leaf.

It is executed in the process of accessing the corresponding data from the root via the intermediate node. In addition, by constructing a tree based on certain rules, it is possible to give the intermediate node the role of an index, and it is possible to streamline access to specific elements.

As an implementation method, an array or cells connected by pointers can be considered, but in general, cells connected by pointers are used in order to respond to changes in the number of elements.

Imagine the following binary search tree that is mentioned in this problem.

As you can see immediately, all the left offspring are smaller than the right parent, and all the right offspring are larger than the parent node.

In this situation, when retrieving an element, it is sufficient to judge whether the corresponding data is larger or smaller than the parent element in order from the root, and when adding an element on top of that, the same processing is performed to find a new place. The advantage is that it is easy to understand whether to add a node. When deleting an element, if there is one child to fill the hole after deleting it, the element is inserted in the hole as it is, and if there are two, the smaller one is inserted in the hole. Is required.

So far we have talked about the structure of trees and binary search trees. Now let's move on to the problem.

Apparently given a binary search tree named root, the goal seems to be to create a function that returns the sum of L and R, that is, all the nodes between the left and right nodes. There is a restriction that all values are unique.

I thought it would be easier to understand if I thought about it in a diagram, so I made a diagram using the example given. root = [10,5,15,3,7,null,18], L = 7, R = 15

If you create a binary search tree based on the given conditions in Example 1, it will look like this, and the sums obtained here are L = 7 and R = 15, so 7 + 10 + 15 = 32. It should be noted here that 5 is not included. Certainly, if you follow the nodes in order, 5 will pass, but since it is the sum of the values included between L = 7 and R = 15, 5 is not included.

# 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:
        def dfs(node):
            if node:
                if L <= node.val <= R:
                    self.ans += node.val
                if L < node.val:
                    dfs(node.left)
                if R > node.val:
                    dfs(node.right)
        self.ans = 0
        dfs(root)
        return self.ans
# Runtime: 224 ms, faster than 82.22% of Python3 online submissions for Range Sum of BST.
# Memory Usage: 21.9 MB, less than 7.92% of Python3 online submissions for Range Sum of BST.

The idea is to compare the values of L and R with the value of node while there is a given value of node, add to the sum if L <= node.value <= R, otherwise than L Implement a function dfs (depth first search) that moves to the left node if node.value is large, and moves to the right node if node.value is smaller than R, and use that to calculate the sum. It is a method of issuing.

Depth-first search is a search from node to node according to the connection relationship of edges to children and grandchildren, and is explained in the following article in a very easy-to-understand manner. [DFS (Depth-first Search) Super Introduction! ~ Entrance to the world of graph algorithms ~ [Part 1]](https://qiita.com/drken/items/4a7869c5e304883f539b#3-%E6%B7%B1%E3%81%95%E5%84%AA% E5% 85% 88% E6% 8E% A2% E7% B4% A2-dfs-% E3% 81% A8% E5% B9% 85% E5% 84% AA% E5% 85% 88% E6% 8E% A2 % E7% B4% A2-bfs)

In addition, there is another way of thinking that uses recurrence. An easy-to-understand example is [here](https://leetcode.com/problems/range-sum-of-bst/discuss/192019/JavaPython-3-3-similar-recursive-and-1-iterative-methods-w- comment-and-analysis.).

def rangeSumBST(self, root: TreeNode, L: int, R: int) -> int:
        if not root:
            return 0
        elif root.val < L:
            return self.rangeSumBST(root.right, L, R)
        elif 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)
# Runtime: 244 ms, faster than 47.97% of Python3 online submissions for Range Sum of BST.
# Memory Usage: 22.1 MB, less than 5.94% of Python3 online submissions for Range Sum of BST.

This problem is very easy to think of as an example of tree structure, binary search tree, and dfs, so I recommend you to try it out.