This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

This is the sum of the scope of the binary search tree on LeetCode. The difficulty is simple.

Tag: “Tree search”, “DFS”, “BFS”

Given root of the binary search tree, 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 the range [1, 2 * 10410^4104]
  • 1 <= Node.val <=
    1 0 5 10^5
  • 1 <= low <= high <=
    1 0 5 10^5
  • All node.val are different

The basic idea

This is one of many “binary search tree traversal” problems.

The middle order traversal of a binary search tree is ordered.

As long as the “middle order traversal” can get the ordered list, in the traversal process to judge whether the node values meet the requirements, for the requirements of the node values can be accumulated.

Middle order traversal of binary search tree can be divided into two forms: iteration and recursion. Given the value range [low,high][low, high][low,high], some pruning can be done during traversal without affecting the space-time complexity.

recursive

Recursion is very simple, one of the simplest implementations of tree traversal.

Code:

class Solution {
    int low, high;
    int ans;
    public int rangeSumBST(TreeNode root, int _low, int _high) {
        low = _low; high = _high;
        dfs(root);
        return ans;
    }
    void dfs(TreeNode root) {
        if (root == null) return;
        dfs(root.left);
        if(low <= root.val && root.val <= high) ans += root.val; dfs(root.right); }}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(n)O(n)O(n)

The iteration

Iteration is actually the use of “stack” to simulate the recursive process, is also a common form of tree traversal implementation.

When asked about tree traversal in a simple interview, the interviewer will not be satisfied with “recursive” solutions, so it is also important to master “iterative/non-recursive” writing.

Code:

class Solution {
    public int rangeSumBST(TreeNode root, int low, int high) {
        int ans = 0;
        Deque<TreeNode> d = new ArrayDeque<>();
        while(root ! =null| |! d.isEmpty()) {while(root ! =null) {
                d.addLast(root);
                root = root.left;
            }
            root = d.pollLast();
            if (low <= root.val && root.val <= high) {
                ans += root.val;
            }
            root = root.right;
        }
        returnans; }}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(n)O(n)O(n)

The last

This is the No.938 article in our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics in LeetCode by the start date, some of which have locks.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.