其他
全国政协委员提议:建议取消公务员35岁门槛。。。
(关注数据结构和算法,了解更多新知识)
最近关于35岁年龄的问题在两会中又被提前了,我记得这个问题应该不止一次被提了,这次是全国政协委员蒙曼提议:取消公务员35岁门槛。对于这个建议各位网友也是拍手称快,统统支持这个提议。
不过我想说的是不光是公务员,其他所有行业也都应该取消35岁年龄的限制。尤其是程序员,大家都在承受年龄的困扰和焦虑,辛辛苦苦在工作中积累了那么多经验,学了那么多知识,最后还是被无情的抛弃。希望这次提议能够被采纳。
--------------下面是今天的算法题--------------
来看下今天的算法题,这题是LeetCode的第429题:N 叉树的层序遍历。实际上它和二叉树的层序遍历非常类似,我们来看下。
问题描述
难度:中等
给定一个 N 叉树,返回其节点值的层序遍历。(即从左到右,逐层遍历)。树的序列化输入是用层序遍历,每组子节点都由 null 值分隔(参见示例)。
输入:root = [1,null,3,2,4,null,5,6]
输出:[[1],[3,2,4],[5,6]]
输入:root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出:[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]
树的高度不会超过 1000
树的节点总数在 [0, 10^4] 之间
问题分析
public List<List<Integer>> levelOrder(Node root) {
List<List<Integer>> ans = new ArrayList<>();
if (root == null)
return ans;
Queue<Node> queue = new LinkedList<>();// 创建队列
queue.offer(root);// 根节点添加到队列中
while (!queue.isEmpty()) {
// 当前层的集合
List<Integer> mList = new ArrayList<>();
int size = queue.size(); // 当前层节点的个数
while (size-- > 0) {
Node cur = queue.poll();
mList.add(cur.val);
// 当前节点的所有子节点添加到队列中
queue.addAll(cur.children);
}
ans.add(mList);// 当前层的集合添加到ans中
}
return ans;
}
public:
vector<vector<int>> levelOrder(Node *root) {
vector<vector<int>> ans;
if (root == nullptr)
return ans;
queue<Node *> q;// 创建队列
q.push(root);// 根节点添加到队列中
while (!q.empty()) {
// 当前层的集合
vector<int> mList;
int size = q.size(); // 当前层节点的个数
while (size-- > 0) {
Node *cur = q.front();
q.pop();
mList.push_back(cur->val);
// 当前节点的所有子节点添加到队列中
for (Node *child: cur->children)
q.push(child);
}
ans.push_back(mList);// 当前层的集合添加到ans中
}
return ans;
}
int **levelOrder(struct Node *root, int *returnSize, int **returnColumnSizes) {
*returnSize = 0;
int **ans = malloc(sizeof(int *) * 1000);
*returnColumnSizes = malloc(sizeof(int) * 1000);// 要在return之前初始化(先初始化)
if (root == NULL)
return ans;
memset(*returnColumnSizes, 0, sizeof(int) * 1000);
struct Node **q = (struct Node **) malloc(sizeof(struct Node *) * 10000);// 创建队列
int left = 0, right = 0;// 左闭右开
q[right++] = root;// 把根节点添加到队列中
while (left != right) {
int size = right - left;// 当前层节点的个数
// 当前层的集合
ans[*returnSize] = malloc(sizeof(int) * size);
while (size-- > 0) {
struct Node *cur = q[left++];// 节点出队
ans[*returnSize][(*returnColumnSizes)[*returnSize]++] = cur->val;
// 当前节点的所有子节点添加到队列中
for (int j = 0; j < cur->numChildren; j++)
q[right++] = cur->children[j];
}
(*returnSize)++;
}
free(q);
return ans;
}
def levelOrder(self, root: 'Node') -> List[List[int]]:
ans = []
if root is None:
return ans
q = deque([root]) # 创建队列
while q:
mList = [] # 当前层的集合
size = len(q) # 当前层节点的个数
for _ in range(size):
cur = q.popleft()
mList.append(cur.val)
# 当前节点的所有子节点添加到队列中
q.extend(cur.children)
ans.append(mList) # 当前层的集合添加到ans中
return ans