这哥们儿估计当场懵了。
干活干得好好的，大群里突然被艾特，说你别直接 git pull 啊，提交记录会被你拉乱，后面查问题都不好查。那场面，换谁谁不尴尬。
更真实的是，他还补了一句：我都这么用三年了，没人说过啊。 哈哈，这才是职场里最常见的坑。不是你不会，而是很多东西没人教，大家默认你应该懂。等真出事了，才在群里公开处刑。
其实不少人用 git pull ，就是图省事，拉一下代码继续干。至于背后到底是 merge 还是 rebase，提交线会不会绕成一团，平时根本没人细看。
但大厂项目人一多，这玩意儿确实容易炸。你一个 merge 节点，我一个 merge 节点，历史记录看着跟毛线球一样。出了 bug 再追，脑瓜子都疼。
二叉树的直径，坑不在递归，坑在你以为自己算的是“最长路径”，结果代码里一直在算“树高”。
这题我第一次看也觉得简单，左子树高度 + 右子树高度，不就完了么。问题是，最长路径不一定经过根节点。它可能藏在某个左子树里面，也可能藏在右子树里面，根节点压根没参与。
比如这棵树：
1
/ \
2 3
/ \
4 5
最长路径是：
4 -> 2 -> 5
长度是 2 条边。
注意，是边数，不是节点数。这里很多人会顺手返回 3，因为路径上有 3 个节点。LeetCode 这题要的是边数，这个地方我一般会先盯一眼，不然调半天都觉得自己没错。
这题真正好用的做法，是递归算每个节点往下能走多深。顺手在递归过程中，把“经过当前节点的最长路径”更新一下。
代码可以这么写：
functiondiameterOfBinaryTree(root) {
let maxPath = 0;
functionheight(node) {
if (node === ) {
return0;
}
const leftHeight = height(node.left);
const rightHeight = height(node.right);
// 当前节点如果作为拐点，最长路径就是左边深度 + 右边深度
const pathThroughNode = leftHeight + rightHeight;
if (pathThroughNode > maxPath) {
maxPath = pathThroughNode;
}
// 返回给父节点时，只能选一边往上接
returnMath.max(leftHeight, rightHeight) + 1;
}height(root);
return maxPath;
}
这里有个细节别写歪了。
更新答案时用的是：
leftHeight + rightHeight
返回高度时用的是：
Math.max(leftHeight, rightHeight) + 1
这两个东西不是一回事。
当前节点自己算直径时，可以左边拿一条，右边拿一条，拼起来。
但当前节点往父节点返回时，只能返回一条链。你不可能左手牵着左子树，右手牵着右子树，再让父节点继续接上去，那就不是一条路径了，树都被你走成网了。
可以拿刚才那棵树跑一下。
节点 4，高度是 1。
节点 5，高度是 1。
到了节点 2，左边高度 1，右边高度 1，所以经过节点 2 的路径长度是：
1 + 1 = 2
maxPath 更新为 2。
节点 2 往上返回高度时，只能返回：
Math.max(1, 1) + 1 = 2
到了根节点 1，左边高度 2，右边高度 1，经过根节点的路径长度是 3，也就是：
4 -> 2 -> 1 -> 3
所以最终答案会变成 3。
这就是递归这题的手感：一边向下拿高度，一边顺手更新全局最长路径。
如果非要把它写成“每个节点都重新算左右高度”，也能做，但那种写法会重复扫很多节点。树一歪，时间复杂度就不好看了。
上面这个写法，每个节点只进一次递归。
时间复杂度 O(n)。
空间复杂度看递归栈，最坏 O(n)，树比较平衡就是 O(log n)。
热门跟贴