卧槽，这就是上海的工资水平吗？
程
老鬼约 3 分钟
老鬼约 3 分钟刚刷到个大厂员工的吐槽，说看到上海平均月薪3万，直接一句“卧槽”。
你说3万在上海算不算高？肯定高啊，起码对大多数打工人来说非常不错。
但问题是，平均这俩字，老板一个月几十万，组长几万，实习生几千，最后一平均，大家都体面了。
最扎心的是，很多人不是没努力，是工资还没追上房租、通勤和外卖涨价的速度。看完只想说，上海的工资水平我羡慕，上海的消费水平我先告辞。
面试题：四叉树交集
四叉树交集这题，名字有点坑人。
它不是让你做两个集合的 AND，而是做两个四叉树表示的矩阵 OR。也就是某个区域里，只要有一棵树是 true，结果就是 true。
我第一次看这题，最容易写歪的地方不是递归，而是叶子节点的处理顺序。
四叉树节点大概长这样：
classNode{
publicboolean val;
publicboolean isLeaf;
public Node topLeft;
public Node topRight;
public Node bottomLeft;
public Node bottomRight;
publicNode(){}
publicNode(boolean val, boolean isLeaf){
this.val = val;
this.isLeaf = isLeaf;
}
publicNode(boolean val, boolean isLeaf,
Node topLeft, Node topRight,
Node bottomLeft, Node bottomRight){
this.val = val;
this.isLeaf = isLeaf;
this.topLeft = topLeft;
this.topRight = topRight;
this.bottomLeft = bottomLeft;
this.bottomRight = bottomRight;
}
}
这题我一般不急着拆四个子节点，先看叶子。
如果 quadTree1 是叶子，并且值是 true，那后面不用看了。因为 true OR anything 都是 true。
if (a.isLeaf && a.val) {
returnnew Node(true, true);
}
同理，第二棵树如果是 true 叶子，也可以直接返回。
如果某棵树是 false 叶子，那它对结果没贡献，结果就等于另一棵树。
if (a.isLeaf && !a.val) {
return b;
}
if (b.isLeaf && !b.val) {
return a;
}
这几行很关键。很多人一上来就递归四个方向，代码看着完整，实际上做了不少没必要的事。
完整写法我会这样写：
classSolution{
public Node intersect(Node a, Node b){
if (a.isLeaf) {
return a.val ? new Node(true, true) : b;
}
if (b.isLeaf) {
return b.val ? new Node(true, true) : a;
}
Node leftTop = intersect(a.topLeft, b.topLeft);
Node rightTop = intersect(a.topRight, b.topRight);
Node leftBottom = intersect(a.bottomLeft, b.bottomLeft);
Node rightBottom = intersect(a.bottomRight, b.bottomRight);
if (leftTop.isLeaf && rightTop.isLeaf
&& leftBottom.isLeaf && rightBottom.isLeaf
&& leftTop.val == rightTop.val
&& rightTop.val == leftBottom.val
&& leftBottom.val == rightBottom.val) {
returnnew Node(leftTop.val, true);
}
returnnew Node(false, false, leftTop, rightTop, leftBottom, rightBottom);
}
}
最后那个合并判断也别漏。
比如四个子区域最后都算成了 true，那结果没必要继续挂四个子节点，直接压成一个叶子节点就行。
这一步不是为了好看，是四叉树题的基本规矩：能合并就合并。不合并的话，结果逻辑上也许对，但树结构不是最简，测试用例很可能不认。
这题递归入口其实就两种情况：
一种是碰到叶子，直接利用 OR 的短路规则处理。
另一种是两边都不是叶子，那就老老实实拆成四块递归。
别把它想复杂。四叉树题看着像数据结构，真正考的还是这几个边界判断有没有排干净。