How to Sum within A Range in a Binary Search Tree?

  • 时间：2020-10-12 15:39:01
  • 分类：网络文摘
  • 阅读：87 次

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

Example 2:
Input: root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10
Output: 23

Note:
The number of nodes in the tree is at most 10000.
The final answer is guaranteed to be less than 2^31.

Given a BST, we can bruteforce the nodes using Depth First Search, Breadth First Search, and any tree traversal approaches e.g. pre-order, post-order or in-order.

However, as the binary tree is BST, if the current node is smaller than the lower bound, we don’t need to traverse its left tree, and similarly, if the node is larger than the upper bound, we don’t need to check its right tree.

Iterative Algorithm of Computing Range Sum in BST

Let’s create a stack and push the root node if not empty. We update the sum if the current node is within the given range, and push the left and/or right node to the stack if it makes sense.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int rangeSumBST(TreeNode* root, int L, int R) {
        int ans = 0;
        stack<TreeNode*> st;
        if (root == NULL) return 0;
        st.push(root);
        while (st.size() > 0) {
            auto p = st.top();
            st.pop();
            if (p != NULL) {
                if (p->val >= L && p->val <= R) {
                    ans += p->val;   // update the sum
                }
                if (L < p->val) {
                    st.push(p->left);  // push left tree
                }
                if (p->val < R) {
                    st.push(p->right);  // push the right tree
                }
            }
        }
        return ans;
    }
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int rangeSumBST(TreeNode* root, int L, int R) {
        int ans = 0;
        stack<TreeNode*> st;
        if (root == NULL) return 0;
        st.push(root);
        while (st.size() > 0) {
            auto p = st.top();
            st.pop();
            if (p != NULL) {
                if (p->val >= L && p->val <= R) {
                    ans += p->val;   // update the sum
                }
                if (L < p->val) {
                    st.push(p->left);  // push left tree
                }
                if (p->val < R) {
                    st.push(p->right);  // push the right tree
                }
            }
        }
        return ans;
    }
};

For tree problems, most have O(N) time complexity and space complexity where N is the number of the nodes in a tree.

Recursion of Computing Range Sum in BST

The same idea can be implemented using recursion where the stack can be maintained automatically by the compiler.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int rangeSumBST(TreeNode* root, int L, int R) {
        ans = 0;
        dfs(root, L, R);
        return ans;
    }
    
private:
    void dfs(TreeNode* root, int L, int R) {
        if (root == NULL) return;
        if (root->val >= L && root->val <= R) {
            ans += root->val;    // update the sum
        }
        if (root->val >= L) { // search the left tree
            dfs(root->left, L, R);
        }
        if (root->val <= R) { // search the right tree
            dfs(root->right, L, R);
        }
    }
    
    int ans;
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int rangeSumBST(TreeNode* root, int L, int R) {
        ans = 0;
        dfs(root, L, R);
        return ans;
    }
    
private:
    void dfs(TreeNode* root, int L, int R) {
        if (root == NULL) return;
        if (root->val >= L && root->val <= R) {
            ans += root->val;    // update the sum
        }
        if (root->val >= L) { // search the left tree
            dfs(root->left, L, R);
        }
        if (root->val <= R) { // search the right tree
            dfs(root->right, L, R);
        }
    }
    
    int ans;
};

The BST tree allows up to check if the node has been fallen in the range, and avoid searching outside the boundary – which speeds up the process.

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读：
简便计算题：1997÷(1997+1997/1998)+(1/1999)　 数学题:在比例尺1：5000的图纸上　 2014年是平年还是闰年　 数学题:在11次红灯变绿灯之间的黄灯亮起中　 奥数题:从这两堆煤中分别运走同样的吨数后　 数学题:用4cm长的线段表示实际距离1200km　 数学题:一根圆柱形木头小明的爸爸将它锯成4段　 奥数题:当王明在100m赛跑冲到终点时，领先刘铭10m　 数学题:小敏要买一些圣诞卡　 奥数题:一列火车匀速速度向北缓缓驶去　
评论列表
添加评论