【Day01】938.二叉搜索树的范围和

最近决定巩固一下算法,开始刷leetcode每日一题,具体刷多久还不知道,刚开始是有点吃力,慢慢来。

【Day01】938.二叉搜索树的范围和

题目:

给定二叉搜索树的根结点 root,返回值位于范围 [low, high] 之间的所有结点的值的和。

示例1:

输入:root = [10,5,15,3,7,null,18], low = 7, high = 15
输出:32

示例 2:

输入:root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
输出:23

提示:

  • 树中节点数目在范围 [1, 2 * 104] 内
  • 1 <= Node.val <= 105
  • 1 <= low <= high <= 105
  • 所有 Node.val 互不相同

题解:

递归

class Solution {
public:
    int rangeSumBST(TreeNode* root, int low, int high) {
        if (!root) return 0;
        int sum = 0;
        sum += rangeSumBST(root->left, low, high);
        if (root->val >= low && root->val <= high) sum += root->val;
        sum += rangeSumBST(root->right, low, high);
        return sum;
    }
};

非递归

class Solution {
public:
    int rangeSumBST(TreeNode* root, int low, int high) {
        if (!root) return 0;
        queue q;
        TreeNode* p = root;
        int sum = 0;
        while (p || q.size()) {
            while (p) {
                q.push(p);
                p = p->left;
            }
            if (q.size()) {
                p = q.front();
                q.pop();
                if (p->val >= low && p->val <= high) {
                    sum += p->val;
                }
                p = p->right;       
            }    
        }
        return sum;
    }
};

   转载规则


《【Day01】938.二叉搜索树的范围和》 Tyzhao 采用 知识共享署名 4.0 国际许可协议 进行许可。
  目录