This is the fifth day of my participation in the More text Challenge. For details, see more text Challenge

Scope sum of binary search tree (Question Number 938)

The title

Given the root node of the binary search tree root, return the sum of the values of all nodes in the range [low, high].

Example 1:

Input: root = [10,5,15,3,7,null,18], low = 7, high = 15 output: 32Copy the code

Example 2:

Input: root = [10,5,15,3,7,13,18,1, null, 6], low = 6, high output = 10:23Copy the code

Tip:

  • The number of nodes in the tree is in range[1, 2 * 104] 内
  • 1 <= Node.val <= 105
  • 1 <= low <= high <= 105
  • allNode.valEach other is not the same

link

Leetcode-cn.com/problems/ra…

explain

This problem, this problem is actually pruning, as long as you write the pruning conditions, the rest is actually very easy.

So let’s look at the problem first, this is a binary search tree, so we don’t have to find all the nodes. The value of the left subtree of a node must be smaller than the value of the current node, and the value of the right subtree must be larger than the value of the current node.

The pruning condition is obvious. If the value of the current node is less than the minimum, then the value of the left subtree is not considered; Similarly, if the value of the current node is larger than the maximum value, then the value of the right subtree is not considered.

It’s that simple, so let’s look at recursion and iteration.

Your own answer (iteration)

var rangeSumBST = function(root, low, high) {
  var res = 0
      stack = [root]
  while (stack.length) {
    root = stack.pop()
    if (root.val < low) {
      root.right && stack.push(root.right)
      continue
    }
    if (root.val > high) {
      root.left && stack.push(root.left)
      continue
    }
    root.left && stack.push(root.left)
    root.right && stack.push(root.right)
    res += root.val
  }
  return res
};
Copy the code

Very simply, if the value of the current node is less than the minimum, just push its right subtree onto the stack and end the iteration. And the same thing can be done if it’s greater than the maximum. If not, prove that the value of this node is between the maximum and minimum, push the left and right subtrees on the stack and accumulate the RES.

Your own answer (recursion)

Recursion is also very simple, so instead of creating a new recursive function for convenience, just call the original function.

var rangeSumBST = function(root, low, high) { if (! root) return 0 if (root.val < low) return rangeSumBST(root.right, low, high) if (root.val > high) return rangeSumBST(root.left, low, high) return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high) };Copy the code

The first is the terminating condition of the recursion, which ends when the node is null, because it has reached the end of the recursion.

Then, if the current node is less than the minimum value, return the recursive result of the right subtree, and if the current node is greater than the maximum value, return the recursive result of the left subtree.

If the current node is between the maximum and minimum, then the sum of the left and right recursive results plus the current node value is returned.

Recursive code seems to be simpler than iterative code, but it’s better to know two solutions than one.

A better answer

There is no




PS: To view past articles and titles, click on the link below:

Here’s 👇 by date

Front Brush path – Directory (Date classification)

After some friends remind, the feeling should also be classified according to the type of questions here is in accordance with the type of 👇

Front brush problem path – Catalogue (Question type classification)

Those who are interested can also check out my personal homepage 👇

Here is RZ