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.

スクリーンショット 2020-04-27 1.42.37.png

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.

スクリーンショット 2020-04-27 1.59.14.png

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

スクリーンショット 2020-04-27 2.28.33.png

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.

Recommended Posts

Let Code Day4 starting from scratch "938. Range Sum of BST"
Let Code Day75 starting from scratch "15.3 Sum"
Let Code Day 39 "494. Target Sum" starting from scratch
Let Code Day 33 "1. Two Sum" starting from scratch
Let Code Day8 starting from scratch "1302. Deepest Leaves Sum"
Let Code Day 32 "437. Path Sum III" starting from scratch
Let Code Day 29 "46. Permutations" starting from scratch
Let Code Day 65 "560. Subarray Sum Equals K" starting from scratch
Let Code Day 27 "101. Symmetric Tree" starting from scratch
Let Code Day 41 "394. Decode String" starting from scratch
Let Code Day56 Starting from Zero "5453. Running Sum of 1d Array"
Let Code Day 25 "70. Climbing Stairs" starting from scratch
Let Code Day69 starting from scratch "279. Perfect Squares"
Let Code Day85 starting from scratch "6. ZigZag Conversion"
Let Code Day 88 "139. Word Break" starting from scratch
Let Code Day 28 "198. House Robber" starting from scratch
Let Code Day 36 "155. Min Stack" starting from scratch
Let Code Day 17 "169. Majority Element" starting from scratch
Let Code Day 23 "226. Invert Binary Tree" starting from scratch
Let Code Day 22 starting from scratch "141. Linked List Cycle"
Let Code Day 30 starting from scratch "234. Palindrome Linked List"
Let Code Day68 starting from scratch "709. To Lower Case"
Let Code Day 44 "543. Diameter of Binary Tree" starting from zero
Let Code Day 26 starting from scratch "94. Binary Tree Inorder Traversal"
Let Code Day 46 starting from scratch "406. Queue Reconstruction by Height"
Let Code Day 31 starting from scratch "581. Shortest Unsorted Continuous Subarray"
Let Code Day 38 starting from scratch "208. Implement Trie (Prefix Tree)"
Let Code Day3 starting from scratch "1313. Decompress Run-Length Encoded List"
Let Code Day87 Starting from Zero "1512. Number of Good Pairs"
Let Code Day7 starting from zero "104. Maximum Depth of Binary Tree"
Let Code Day92 Starting from Zero "4. Median of Two Sorted Arrays"
Let Code Day 77 starting from scratch "1502. Can Make Arithmetic Progression From Sequence"
Let Code Day 76 starting from scratch "3. Longest Substring Without Repeating Characters"
Let Code Day 35 "160. Intersection of Two Linked Lists" Starting from Zero
Let Code Day72 Starting from Zero "1498. Number of Subsequences That Satisfy the Given Sum Condition"
Let Code Day58 Starting from Zero "20. Valid Parentheses"
Let Code Day16 Starting from Zero "344. Reverse String"
Let Code Day49 starting from zero "1323. Maximum 69 Number"
Let Code Day89 "62. Unique Paths" Starting from Zero
Let Code Day 55 "22. Generate Parentheses" Starting from Zero
Let Code Table of Contents Starting from Zero
Let Code Day18 starting from zero "53. Maximum Subarray"
Let Code Day 13 "338. Counting Bits" Starting from Zero
Let Code Day71 Starting from Zero "1496. Path Crossing"
Let Code Day 61 "7. Reverse Integer" starting from zero
Let Code Day 82 "392. Is Subsequence" Starting from Zero
Let Code Day51 Starting from Zero "647. Palindromic Substrings"
Let Code Day 50 "739. Daily Temperatures" Starting from Zero
Let Code Day 15 "283. Move Zeroes" starting from zero
Let Code Day14 starting from zero "136. Single Number"
Let Code Day 9 "701. Insert into a Binary Search Tree" starting from scratch
Let Code Day 80 "703. Kth Largest Element in a Stream" starting from scratch
Let Code Day6 Starting from Zero "1342. Number of Steps to Reduce a Number to Zero"
Let Code Day 43 "5. Longest Palindromic Substring" Starting from Zero
Let Code Day74 starting from zero "12. Integer to Roman"
Let Code Day 42 "2. Add Two Numbers" Starting from Zero
Let Code Day57 Starting from Zero "35. Search Insert Position"
Let Code Day47 Starting from Zero "14. Longest Common Prefix"
Let Code Day78 Starting from Zero "206. Reverse Linked List"
Let Code Day 90 starting from scratch "101 11. Capacity To Ship Packages Within D Days"
Let Code Day10 Starting from Zero "1431. Kids With the Greatest Number of Candies"