刚看到个贴子,说网友晋升答辩那天准备了20页PPT,把一年成绩吹到天上去,结果评委就问了一句:你在这个项目里的不可替代性是啥?他当场哑火。最后才发现晋升名单早就定好了,答辩只是走流程。
我觉得这事吧,先别只骂职场黑。名单提前定,其实很多公司都是默认操作:平时表现、资源、老板的信任度,早就盘好了,答辩只是给所有人一个“说得过去的理由”。难听点,是形式;好听点,是程序正义。
但这事也敲了个重点:你值不值钱,不在PPT有几页,而在别人心里有没有“非你不可”的印象。
换个角度想,答辩未必改变结果,但可以逼你回答那个关键问题:如果把你从项目里抽走,会少点什么?能把这点想明白,晋不晋升都不亏。总的来说,认清现实不等于躺平,看清游戏规则,才有机会改写规则。
面试题:拆分二叉搜索树
昨晚十一点多吧,我在公司楼下买了个关东煮,刚坐回工位,小李就凑过来问我:“哥,有个题,拆分二叉搜索树,咋写才能又短又不容易写崩?”我当时脑子有点木,手还烫着,嘴里就开始瞎念叨——你把 BST 想成仓库的分拣线就行了,阈值 V 就是“这边走普快,那边走加急”,关键是你不能把包裹拆烂了,你得保持原来的结构,最多就是把某些指针掰到另一条线去。
二叉搜索树你们都知道吧,左边都小,右边都大。现在要拆成两棵:一棵全是 <= V,另一棵全是 > V。很多人第一反应是中序遍历一遍然后重建,两趟,还得存数组,写着写着就开始溢出、空指针、还有重建不小心把平衡性搞没了……其实完全没必要。这个题最爽的是“顺着 BST 的性质一路往下走”,像你在快递站只看面单,不会把每个快递都打开检查,对吧。
我一般这么想:你站在当前 root,看它的值 root.val。
- 如果
root.val <= V,那 root 这个包裹肯定属于“左边那堆”(<=V 那棵树)。那问题出在哪?出在它的右子树里可能混着比 V 大的东西。于是你对 root.right 递归去拆,拆回来会得到两棵:一棵 <=V 的,一棵 >V 的。然后把“<=V 那棵”接回到 root.right,因为这部分还是应该跟着 root 留在左边;而“>V 那棵”就作为最终结果的右边那棵树返回。 - 反过来,如果
root.val > V,root 必须去右边那棵(>V)。那它的左子树里可能有 <=V 的,递归拆 root.left,拆回来的“>V 那棵”接回 root.left,剩下那棵 <=V 作为最终左树返回。
就这个味儿,真的就像你分拣的时候:当前这箱货要进 A 区,那就只需要继续检查它“可能出错的那一侧”,另一侧天然就是对的。说着说着我还打了个哈欠,反正代码就这么几行,给你们贴个 Java 的,都是我自己平时写题那种写法,不搞花里胡哨。
publicclassSplitBST{staticclassTreeNode{int val; TreeNode left, right; TreeNode(int v) { this.val = v; } }// 返回数组 res[0]:所有 <= V 的树;res[1]:所有 > V 的树public TreeNode[] splitBST(TreeNode root, int V) {if (root == null) returnnew TreeNode[]{null, null};if (root.val <= V) {// root 归左树,去拆右子树 TreeNode[] rightSplit = splitBST(root.right, V); root.right = rightSplit[0]; // 把 <=V 的部分接回 root.rightreturnnew TreeNode[]{root, rightSplit[1]}; // >V 的部分独立成右树 } else {// root 归右树,去拆左子树 TreeNode[] leftSplit = splitBST(root.left, V); root.left = leftSplit[1]; // 把 >V 的部分接回 root.leftreturnnew TreeNode[]{leftSplit[0], root}; // <=V 的部分独立成左树 } }}
你看这个写法就很“抠门”,全程不新建节点,只是改指针,所以空间基本就是递归栈。复杂度也挺直观:每个节点最多走一次,O(n)。我当时还顺手给小李举了个例子:比如树里有 4 当根,左边 2,右边 6,再挂点 1、3、5、7,V=2,那最后左树就是 2(1, null),右树就是 4(3,6...) 这种感觉——不是按值重排,是“原样剪开”。
哦对了,坑也不是没有,主要就两个:一个是别搞错“接回去的是哪一半”,<=V 那半接到左树那边,>V 那半接到右树那边;另一个是你要接受这个结果不保证平衡,题目也没说要平衡,你别自己加戏。行了我先不说了,刚刚钉钉又响了,好像线上又有人把空指针打出来了…我去看一眼。