其他
老板裁员后奇怪：原先100个人干50个人的活，裁掉一半以后，剩下50人干25个人的活，好像并没有提高工作效率。。。
(关注数据结构和算法，了解更多新知识)
最近在网上看到一网友发文说：公司100个人干50个人的活，裁掉一半以后，剩下50人干25个人的活，工作效率并没有提升。CEO的意思是裁掉50人之后，想让剩下的50人继续干50人的活，但是并没有达到他想要的效果。
有网友说：CEO错估了效率，把员工的正常效率放大2倍去估活。我觉得这种可能性是比较大的，本来100个人干100个人的活，而CEO认为这些活50个人就能干完，干脆裁掉一半，结果发现效率并没有提升。
还有的网友说：真正的做到了精准裁员，只裁掉干活的人。就像下面一位网友说的：不干活的去裁员，只能裁掉干活的了。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第103题：二叉树的锯齿形层序遍历，一网友在字节的面试中遇到过这题，我们来看下。
问题描述
难度：中等
给你二叉树的根节点 root ，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[20,9],[15,7]]
输入：root = [1]
输出：[[1]]
树中节点数目在范围 [0, 2000] 内
-100 <= Node.val <= 100
问题分析
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
if (root == null)
return ans;
Queue<TreeNode> queue = new LinkedList<>();// 创建队列
queue.add(root);// 根节点添加到队列中
boolean leftToRight = true;
while (!queue.isEmpty()) {
// 当前层的节点个数
int count = queue.size();
List<Integer> mList = new LinkedList<>();// 当前层的集合
// 遍历这一行的所有节点
for (int i = 0; i < count; i++) {
TreeNode node = queue.poll();
// 判断是从左往右打印还是从右往左打印。
if (leftToRight) {// 从左往右添加到后面
mList.add(node.val);
} else {// 从右往左添加到前面
mList.add(0, node.val);
}
// 左右子节点如果不为空会被加入到队列中
if (node.left != null)
queue.add(node.left);
if (node.right != null)
queue.add(node.right);
}
ans.add(mList);
leftToRight = !leftToRight;// 下一步更改方向
}
return ans;
}
public:
vector<vector<int>> zigzagLevelOrder(TreeNode *root) {
vector<vector<int>> ans;
if (root == nullptr)
return ans;
queue<TreeNode *> nodeQueue;// 创建队列
nodeQueue.push(root);// 根节点添加到队列中
bool leftToRight = true;
while (!nodeQueue.empty()) {
// 当前层的节点个数
int count = nodeQueue.size();
deque<int> levelList;// 当前层的集合
// 遍历这一行的所有节点
for (int i = 0; i < count; i++) {
TreeNode *node = nodeQueue.front();
nodeQueue.pop();
// 判断是从左往右打印还是从右往左打印。
if (leftToRight) {// 从左往右添加到后面
levelList.push_back(node->val);
} else {// 从右往左添加到前面
levelList.push_front(node->val);
}
// 左右子节点如果不为空会被加入到队列中
if (node->left)
nodeQueue.push(node->left);
if (node->right)
nodeQueue.push(node->right);
}
ans.emplace_back(vector<int>{levelList.begin(), levelList.end()});
leftToRight = !leftToRight;// 下一步更改方向
}
return ans;
}
#define N 2001
void reverse(int **ans, int start, int end, const int *returnColumnSizes) {
while (start < end) {
int *tmpArr = ans[start];
int left = 0, right = returnColumnSizes[start] - 1;
while (left < right) {
int tmp = tmpArr[left];
tmpArr[left] = tmpArr[right];
tmpArr[right] = tmp;
left++;
right--;
}
start += 2;
}
}
int **zigzagLevelOrder(struct TreeNode *root, int *returnSize, int **returnColumnSizes) {
int **ans = malloc(sizeof(int *) * N);
*returnSize = 0;
*returnColumnSizes = malloc(sizeof(int) * N);
memset(*returnColumnSizes, 0, sizeof(int) * N);
if (root == NULL)
return ans;
struct TreeNode **nodeQueue = malloc(sizeof(struct TreeNode *) * N); // 创建队列
int left = 0, right = 0;// 左闭右开
nodeQueue[right++] = root;// 根节点添加到队列中
while (left != right) {
// 当前层的节点个数
int count = right - left;
ans[*returnSize] = malloc(sizeof(int) * N);// 当前层的集合
// 遍历这一行的所有节点
for (int i = 0; i < count; i++) {
struct TreeNode *node = nodeQueue[left++];
// 先不要区分方向，最后在反转
ans[*returnSize][(*returnColumnSizes)[*returnSize]++] = node->val;
// 左右子节点如果不为空会被加入到队列中
if (node->left)
nodeQueue[right++] = node->left;
if (node->right)
nodeQueue[right++] = node->right;
}
(*returnSize)++;
}
reverse(ans, 1, *returnSize, *returnColumnSizes);// 反转
free(nodeQueue);
return ans;
}
def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
ans = []
if root is None:
return ans
q = deque([root]) # 创建队列,顺便把根节点添加到队列中
leftToRight = True
while q:
mList = [] # 当前层的集合
# 遍历这一行的所有节点
for _ in range(len(q)):
node = q.popleft()
mList.append(node.val)
# 左右子节点如果不为空会被加入到队列中
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
# 添加的时候注意方向
ans.append(mList if leftToRight else mList[::-1])
leftToRight = not leftToRight # 下一步更改方向
return ans