某大厂员工：直接用git pull拉代码，被diss！|git|node|queue|代码|调用|队列

刚刷到这个吐槽帖，给我看乐了，也有点心虚。

一个大厂同学干活干得好好的，突然被大群艾特，说他不该直接 git pull 拉代码。理由是会把提交历史搞乱，后面排查问题像翻垃圾堆。

他人都懵了：我这操作用了三年啊，项目也没炸，怎么今天突然变成“历史罪人”了？

其实很多人刚进团队都是这么干的，pull 一下，冲突解决一下，能跑就行。结果一进讲究提交树的组，立马被教育。人家要的是线干净，最好 rebase 一下，别动不动 merge 出一堆分叉。

git 这玩意儿，表面是工具，背地里全是门派。

算法题：N 叉树的最大深度

root == 还往下递归，提交直接挂。

这题叫 N 叉树的最大深度 ，看着像二叉树换个名字，实际写的时候最容易错在两个地方：一个是空树返回多少，一个是子节点列表怎么处理。

题目给的是一棵 N 叉树，每个节点不是只有 left、right，而是有一个 children 列表。最大深度就是从根节点到最远叶子节点经过的节点数。

比如这棵树：

 1
/ | \
3 2 4
/ \
5 6

从 1 -> 3 -> 5 这条路走下去，一共 3 个节点，所以最大深度是 3。

这题我一般不先想复杂数据结构，先看一个节点自己能提供什么信息。

一个节点的深度，取决于它所有孩子里面最深的那个。

如果当前节点没有孩子，那它自己就是一层，返回 1。

如果有孩子，就挨个算孩子的最大深度，然后取最大值，最后再加上当前节点这一层。

代码可以写得很短：

import java.util.List;

classNode{
publicint val;
public List children;

publicNode{}

publicNode(int val, List children){
this.val = val;
this.children = children;
}
}

classSolution{
publicintmaxDepth(Node root){
if (root == ) {
return0;
}

int childMaxDepth = 0;

if (root.children != ) {
for (Node child : root.children) {
childMaxDepth = Math.max(childMaxDepth, maxDepth(child));
}
}

return childMaxDepth + 1;
}
}

这里有个细节，不要把初始深度写成 1，然后循环里再加来加去。那样也能写对，但容易绕。

我更喜欢把问题拆成两段：

当前节点下面的孩子，最深是多少？

当前节点自己再占一层。

所以最后是：

return childMaxDepth + 1;

这个写法读起来比较稳，不容易在叶子节点那里出错。

再看几个边界。

空树：

root =

返回 0。

只有一个根节点：

孩子最大深度是 0，加上自己这一层，返回 1。

如果树退化成一条链：

1 -> 2 -> 3 -> 4

每次都只有一个孩子，递归会一路往下，最后一层层返回，结果是 4。

这题递归的时间复杂度没什么花活，每个节点只访问一次，所以是 O(n) 。

空间复杂度主要看递归栈。树如果比较平衡，高度没那么夸张；如果退化成链，递归深度就是 n ，空间复杂度最坏 O(n) 。

如果担心递归太深，也可以用队列按层扫。这个写法更像线上排查树形数据层级时会用的版本，一层一层数，不靠调用栈。

import java.util.ArrayDeque;
import java.util.Deque;

classSolutionByQueue{
publicintmaxDepth(Node root){
if (root == ) {
return0;
}

Deque queue = new ArrayDeque<>;
queue.addLast(root);

int depth = 0;

while (!queue.isEmpty) {
int levelSize = queue.size;
depth++;

for (int i = 0; i < levelSize; i++) {
Node current = queue.pollFirst;

if (current.children == ) {
continue;
}

for (Node child : current.children) {
if (child != ) {
queue.addLast(child);
}
}
}
}

return depth;
}
}