专栏：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算法文档 。
热门跟贴