华为
之前写了 华为今年的校招开奖情况，与其他互联网企业（SP/SSP 占比较多）不同，华为今年对于职级的要求很高。
基本上硕士都是 13 级定薪，即使是双 9 的硕士也是如此，网上已经有同学指出今年性价比根本不够：
职级 13，而且 base 基本都在上海。
虽然之后上海大部队会搬到青浦，但那边的房价已经先于搬迁日期，陆续在涨了，这个我们之前也聊过：华为搬迁，房东赚麻 。
那边的房东基本都把华为员工当财主，甚至试图把毛坯房拿出来出租，想让华为员工替他把大几十万的装修费也出了，十分离谱。
再结合本次华为 OC 的时间基本都在周五 or 周六，连和楼主谈入职的 HR 都通话到晚上 10 点多，由此可见，996 可能只是最低要求。
不少同学也表示，身边不少人都是 allin 华为，或者是 0Offer 选手，不去就没了，与其说是选择华为，不如说是被华为选择：
对此，你怎么看？你会因为华为的名气（而非待遇）优先选择华为吗？欢迎评论区交流。
...
回归主题。
周末，来道简单算法题。
题目描述
平台：LeetCode
题号：993
在二叉树中，根节点位于深度 处，每个深度为 的节点的子节点位于深度 处。
如果二叉树的两个节点深度相同，但 父节点不同 ，则它们是一对堂兄弟节点。
我们给出了具有唯一值的二叉树的根节点 ，以及树中两个不同节点的值 和 。
只有与值 和 对应的节点是堂兄弟节点时，才返回 true，否则，返回 false。
示例 1：
输入：root = [1,2,3,4], x = 4, y = 3
输出：false
示例 2：
输入：root = [1,2,3,null,4,null,5], x = 5, y = 4
输出：true
示例 3：
输入：root = [1,2,3,null,4], x = 2, y = 3
输出：false
提示：
二叉树的节点数介于 到 之间。 每个节点的值都是唯一的、范围为 到 的整数。
DFS
显然，我们希望得到某个节点的「父节点」&「所在深度」，不难设计出如下「DFS 函数签名」：
/**
* 查找 t 的「父节点值」&「所在深度」
* @param root 当前搜索到的节点
* @param fa root 的父节点
* @param depth 当前深度
* @param t 搜索目标值
* @return [fa.val, depth]
*/
int[] dfs(TreeNode root, TreeNode fa, int depth, int t);
之后按照遍历的逻辑处理即可。
需要注意的时，我们需要区分出「搜索不到」和「搜索对象为 （没有 父节点）」两种情况。
我们约定使用 代指没有找到目标值 ，使用 代表找到了目标值 ，但其不存在父节点。
Java 代码：
class Solution {
public boolean isCousins(TreeNode root, int x, int y) {
int[] xi = dfs(root, null, 0, x);
int[] yi = dfs(root, null, 0, y);
return xi[1] == yi[1] && xi[0] != yi[0];
}
int[] dfs(TreeNode root, TreeNode fa, int depth, int t) {
if (root == null) return new int[]{-1, -1}; // 使用 -1 代表为搜索不到 t
if (root.val == t) {
return new int[]{fa != null ? fa.val : 1, depth}; // 使用 1 代表搜索值 t 为 root
}
int[] l = dfs(root.left, root, depth + 1, t);
if (l[0] != -1) return l;
return dfs(root.right, root, depth + 1, t);
}
}
C++ 代码：
class Solution {
public:
bool isCousins(TreeNode* root, int x, int y) {
vector<int> xi = dfs(root, nullptr, 0, x);
vector<int> yi = dfs(root, nullptr, 0, y);
return xi[1] == yi[1] && xi[0] != yi[0];
}
vector<int> dfs(TreeNode* root, TreeNode* fa, int depth, int t) {
if (!root) return {-1, -1}; // 使用 -1 代表为搜索不到 t
if (root->val == t) {
return {fa != nullptr ? fa->val : 1, depth}; // 使用 1 代表搜索值 t 为 root
}
vector<int> l = dfs(root->left, root, depth + 1, t);
if (l[0] != -1) return l;
return dfs(root->right, root, depth + 1, t);
}
};
Python 代码：
class Solution:
def isCousins(self, root: TreeNode, x: int, y: int) -> bool:
xi = self.dfs(root, None, 0, x)
yi = self.dfs(root, None, 0, y)
return xi[1] == yi[1] and xi[0] != yi[0]
def dfs(self, root: TreeNode, fa: TreeNode, depth: int, t: int) -> list:
if not root: return [-1, -1] # 使用 -1 代表为搜索不到 t
if root.val == t:
return [fa.val if fa else 1, depth] # 使用 1 代表搜索值 t 为 root
l = self.dfs(root.left, root, depth + 1, t)
if l[0] != -1: return l
return self.dfs(root.right, root, depth + 1, t)
TypeScript 代码：
function dfs(root: TreeNode | null, fa: TreeNode | null, depth: number, t: number): number[] {
if (!root) return [-1, -1]; // 使用 -1 代表为搜索不到 t
if (root.val === t) {
return [fa ? fa.val : 1, depth]; // 使用 1 代表搜索值 t 为 root
}
const l = dfs(root.left, root, depth + 1, t);
if (l[0] !== -1) return l;
return dfs(root.right, root, depth + 1, t);
}
function isCousins(root: TreeNode | null, x: number, y: number): boolean {
const xi = dfs(root, null, 0, x);
const yi = dfs(root, null, 0, y);
return xi[1] === yi[1] && xi[0] !== yi[0];
};
时间复杂度： 空间复杂度：忽略递归开销为 ，否则为
BFS
能使用 DFS，自然也能使用 BFS，两者大同小异。
Java 代码：
class Solution {
public boolean isCousins(TreeNode root, int x, int y) {
int[] xi = bfs(root, x);
int[] yi = bfs(root, y);
return xi[1] == yi[1] && xi[0] != yi[0];
}
int[] bfs(TreeNode root, int t) {
Deque<Object[]> d = new ArrayDeque<>(); // 存储值为 [cur, fa, depth]
d.addLast(new Object[]{root, null, 0});
while (!d.isEmpty()) {
int size = d.size();
while (size-- > 0) {
Object[] poll = d.pollFirst();
TreeNode cur = (TreeNode)poll[0], fa = (TreeNode)poll[1];
int depth = (Integer)poll[2];
if (cur.val == t) return new int[]{fa != null ? fa.val : 0, depth};
if (cur.left != null) d.addLast(new Object[]{cur.left, cur, depth + 1});
if (cur.right != null) d.addLast(new Object[]{cur.right, cur, depth + 1});
}
}
return new int[]{-1, -1};
}
}
C++ 代码：
class Solution {
public:
bool isCousins(TreeNode* root, int x, int y) {
vector<int> xi = bfs(root, x);
vector<int> yi = bfs(root, y);
return xi[1] == yi[1] && xi[0] != yi[0];
}
vector<int> bfs(TreeNode* root, int t) {
queue<pair<TreeNode*, pair<TreeNode*, int>>> q; // 存储值为 [cur, {fa, depth}]
q.push({root, {nullptr, 0}});
while (!q.empty()) {
int size = q.size();
while (size-- > 0) {
auto poll = q.front(); q.pop();
TreeNode* cur = poll.first;
TreeNode* fa = poll.second.first;
int depth = poll.second.second;
if (cur->val == t) return {fa ? fa->val : 0, depth};
if (cur->left) q.push({cur->left, {cur, depth + 1}});
if (cur->right) q.push({cur->right, {cur, depth + 1}});
}
}
return {-1, -1};
}
};
Python 代码：
class Solution:
def isCousins(self, root: TreeNode, x: int, y: int) -> bool:
xi = self.bfs(root, x)
yi = self.bfs(root, y)
return xi[1] == yi[1] and xi[0] != yi[0]
def bfs(self, root: TreeNode, t: int) -> list:
d = deque([(root, None, 0)]) # 存储值为 [cur, fa, depth]
while d:
size = len(d)
while size > 0:
poll = d.popleft()
cur, fa, depth = poll
if cur.val == t:
return [fa.val if fa else 0, depth]
if cur.left:
d.append((cur.left, cur, depth + 1))
if cur.right:
d.append((cur.right, cur, depth + 1))
size -= 1
return [-1, -1]
TypeScript 代码：
function bfs(root: TreeNode | null, t: number): number[] {
const d: Array<{ cur: TreeNode | null, fa: TreeNode | null, depth: number }> = [{ cur: root, fa: null, depth: 0 }];
while (d.length > 0) {
const size = d.length;
for (let i = 0; i < size; i++) {
const { cur, fa, depth } = d.shift()!;
if (cur && cur.val === t) return fa ? [fa.val, depth] : [0, depth];
if (cur?.left) d.push({ cur: cur.left, fa: cur, depth: depth + 1 });
if (cur?.right) d.push({ cur: cur.right, fa: cur, depth: depth + 1 });
}
}
return [-1, -1];
}
function isCousins(root: TreeNode | null, x: number, y: number): boolean {
const xi = bfs(root, x);
const yi = bfs(root, y);
return xi[1] === yi[1] && xi[0] !== yi[0];
};
时间复杂度： 空间复杂度：
最后
巨划算的 LeetCode 会员优惠通道目前仍可用 ~
使用福利优惠通道 leetcode.cn/premium/?promoChannel=acoier，年度会员 有效期额外增加两个月，季度会员 有效期额外增加两周，更有超大额专属 🧧 和实物 🎁 福利每月发放。
我是宫水三叶，每天都会分享算法知识，并和大家聊聊近期的所见所闻。
欢迎关注，明天见。
