双非仔的春天要来了。。

专栏：50多种数据结构彻底征服

专栏：50多种经典图论算法全部掌握

最近一双非网友发文称一天收到10个公司的笔试，双非仔的春天要来了。我觉得这才是找工作的正确方式，如果学历一般，找工作就应该多投，这样机会才会更多。

有的人担心面试多了，万一他们都给我发offer，我不好意思拒绝，该怎么办？你想多了，先让她们给你发offer在说吧。就算拒绝也很正常，HR在挑人的时候不是一直在拒绝吗，也没见她不好意思。

就像之前一个网友发的，后面都快奔溃了。每天才 5 家，就算是在厉害的学校也不可能每天收到10个offer，所以无论是25届的，还是现在找工作的，大胆投，不要瞻前顾后，这样你的春天就会来了。

该网友收到的面试邀请

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是LeetCode的第938题：二叉搜索树的范围和。

问题描述

来源：LeetCode第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 * 10^4] 内

• 1 <= Node.val <= 10^5

• 1 <= low <= high <= 10^5

• 所有 Node.val 互不相同
  

问题分析

这题让计算 二叉搜索树 中节点值位于[low,high]之间的所有节点之和。一种常规的解决思路就是遍历这棵树的所有节点，然后累加符合条件的节点值。

但这题说的是二叉搜索树，在二叉搜索树中左子树的值都小于根节点，右子树的值都大于根节点，并且每一棵子树也都满足这个条件，我们可以根据这个条件对这题做个优化。

因为右子树的值都比根节点大，所以如果根节点大于high，说明根节点的右子树也都大于high，不满足条件，这个时候就不需要在右子树查找。只有在根节点值小于high的时候，右子树的某些值才有可能小于high。左子树同理。

JAVA：

public int rangeSumBST(TreeNode root, int low, int high) {     if (root == null)         return 0;     int res = 0;     if (root.val >= low && root.val <= high)         res += root.val;     if (root.val < high)         res += rangeSumBST(root.right, low, high);     if (root.val > low)         res += rangeSumBST(root.left, low, high);     return res; }

C++：

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

Python：

def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:     if root is None:         return 0     res = 0     if low <= root.val <= high:         res += root.val     if root.val < high:         res += self.rangeSumBST(root.right, low, high)     if root.val > low:         res += self.rangeSumBST(root.left, low, high)     return res

笔者简介

博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。