神仙公司（成都）
神仙公司，继续。
最近对古城很感兴趣，加上前两周吃的串串还记忆犹新，这期写一下四川省省会：成都。
在互联网人眼中，成都似乎是一个存在感很低的城市，但实际上成都一直稳居"新一线城市榜单"之首。
在这座以「宜人的气候、悠闲的生活方式、丰富的文化和美食」著称的"天府之国"，到底藏着多少适合年轻人就业的神仙公司，一起来看看。
一直很稳的 WLB 典范（神仙公司）：
-
育碧：早 9:00 晚 18:00，不打卡，少数不加班的游戏工作室，标准五险一金，额外补充医疗保险，通讯补贴，工作餐补贴，节日福利，技术氛围拉满，入职 12 天年假，在招岗位大多不限学历，薪资水平 14k~35k，15 薪； -
Naver：早 8:30 晚 17:30，可弹性上下班，双休不卷，全额社保公积金，额外补充医疗保险，15 天年假，12 天带薪病假，工作氛围轻松，办公地点优渥，运维和软件工程师长期在招，薪资范围 12k~44k，13薪~15薪； -
ThoughtWorks：早 9:00 晚 18:00，可弹性上下班，双休不卷，作为一家全球范围都口碑不错的公司，标准五险一金，额外补充医疗保险，还有零食下午茶，节日福利，定期体检等福利，13k~25k，14薪； -
沃尔沃：早 9:00 晚 17:30，双休不卷，足额六险二金，入职有 12 天年假，24 周带薪育儿假，人民关怀拉满，薪资范围 13k~55k，13薪~15薪； -
亚马逊：弹性上班，员工可在 855、965 和 1075 之间选择，一周有两天可居家办公，周三可提前下班去运动，周四和周五不定时下午茶，入职 12 天年假，薪资范围 18k~40k； -
科大讯飞：早 8:30 晚 17:30，双休，五险一金，额外补充医疗保险，免费班车，工作餐补，通讯补贴，节日福利，股票期权，在招岗位 12k~30k，14 薪；
还算不错的企业（半仙公司）：
-
腾讯：是滴，成都也有腾讯，企业微信客户端团队就在成都。相比于深圳总部，成都腾讯节奏较为适中，待遇顶尖。双休，加班少，免费班车，工作餐补贴，零食下午茶，健身房，节日福利，股票期权，在招薪资水平 15k~50k，14薪~16薪； -
字节：相比于一线城市的字节，节奏稍有放松，但不多，胜在待遇顶尖。入职 15 天年假，8 天带薪病假，足额五险一金，免费健身房和年度体检，三餐免费，食堂高标准，每日还有下午茶，在招薪资水平 20k~55k，13薪~16薪（具体看绩效）；
关于「成都」以及「成都神仙公司」，你有什么想分享的呢，欢迎评论区留言。
...
回归主题。
周末，快乐小算法。
题目描述
平台：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
提示：
-
树中节点数目在范围 ] 内 -
-
-
所有 Node.val互不相同
基本思路
这又是众多「二叉搜索树遍历」题目中的一道。
「二叉搜索树的中序遍历是有序的。」
只要对其进行「中序遍历」即可得到有序列表，在遍历过程中判断节点值是否符合要求，对于符合要求的节点值进行累加即可。
二叉搜索树的「中序遍历」有「迭代」和「递归」两种形式。「由于给定了值范围 ，因此可以在遍历过程中做一些剪枝操作，但并不影响时空复杂度。」
递归
递归写法十分简单，属于树的遍历中最简单的实现方式。
Java 代码：
class Solution {
int low, high, 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);
}
}
C++ 代码：
class Solution {
public:
int low, high, ans;
int rangeSumBST(TreeNode* root, int _low, int _high) {
low = _low; high = _high;
dfs(root);
return ans;
}
void dfs(TreeNode* root) {
if (!root) return;
dfs(root->left);
if (low <= root->val && root->val <= high) ans += root->val;
dfs(root->right);
}
};
Python 代码：
class Solution:
def rangeSumBST(self, root: TreeNode, _low: int, _high: int) -> int:
self.low = _low
self.high = _high
self.ans = 0
self.dfs(root)
return self.ans
def dfs(self, root):
if not root:
return
self.dfs(root.left)
if self.low <= root.val <= self.high:
self.ans += root.val
self.dfs(root.right)
-
时间复杂度： -
空间复杂度：
迭代
迭代其实就是使用「栈」来模拟递归过程，也属于树的遍历中的常见实现形式。
一般简单的面试中如果问到树的遍历，面试官都不会对「递归」解法感到满意，因此掌握「迭代/非递归」写法同样重要。
Java 代码：
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;
}
return ans;
}
}
C++ 代码：
class Solution {
public:
int rangeSumBST(TreeNode* root, int low, int high) {
int ans = 0;
deque<TreeNode*> d;
while (root != nullptr || !d.empty()) {
while (root != nullptr) {
d.push_back(root);
root = root->left;
}
root = d.back();
d.pop_back();
if (low <= root->val && root->val <= high) ans += root->val;
root = root->right;
}
return ans;
}
};
Python 代码：
class Solution:
def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:
ans = 0
stk = []
while root is not None or stk:
while root is not None:
stk.append(root)
root = root.left
root = stk.pop()
if low <= root.val <= high:
ans += root.val
root = root.right
return ans
-
时间复杂度： -
空间复杂度：
最后
巨划算的 LeetCode 会员优惠通道目前仍可用 ~
使用福利优惠通道 leetcode.cn/premium/?promoChannel=acoier，年度会员 有效期额外增加两个月，季度会员 有效期额外增加两周，更有超大额专属 🧧 和实物 🎁 福利每月发放。
我是宫水三叶，每天都会分享算法知识，并和大家聊聊近期的所见所闻。
欢迎关注，明天见。
更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉
