其他
网友：过年回家，年薪40多万的我被鄙视了，感觉他们人均年薪六七十万。。。
(关注数据结构和算法，了解更多新知识)
最近一网友发文称：自己年薪四五十万被鄙视了，感觉他们人均年收入六七十万，从小成绩优秀的我，现在却成了吊尾车。该网友IP显示的是山东，我不知道山东人均收入多少，但我感觉年薪四五十万也算是高薪了吧，即便是在一线城市的北上广深也不至于被别人鄙视。
当然中国有句话叫：物以类聚人以群分。他之所以被鄙视应该是他身边人的收入都普遍比较高。
我们来看下网友的评论，有的网友说：老家很多人做抖音带货，收入超高，秒杀月薪三四万的打工人。还有的说：可能你的圈子比较有钱。还有的说：没事，回家之后身份都是自己给的。
--------------下面是今天的算法题--------------
下面来看一道算法题，这题是LeetCode的第107题：二叉树的层序遍历 II，实际上就是二叉树的BFS遍历，前面我们也做过类似的，我们来看下。
问题描述
难度：中等
给你二叉树的根节点 root ，返回其节点值自底向上的层序遍历。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
输入：root = [3,9,20,null,null,15,7]
输出：[[15,7],[9,20],[3]]
输入：root = [1]
输出：[[1]]
树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000
问题分析
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> ans = new LinkedList<>();
dfs(ans, root, 0);
return ans;
}
public void dfs(List<List<Integer>> ans, TreeNode root, int level) {
if (root == null)
return;
// 初始化下一层的集合
if (level == ans.size())
ans.add(0, new ArrayList<>());
// 这里就相当于从下往上打印了
ans.get(ans.size() - level - 1).add(root.val);
// 递归左右子树
dfs(ans, root.left, level + 1);
dfs(ans, root.right, level + 1);
}
public:
vector<vector<int>> levelOrderBottom(TreeNode *root) {
vector<vector<int>> ans;
dfs(ans, root, 0);
reverse(ans.begin(), ans.end());// 反转
return ans;
}
void dfs(vector<vector<int>> &ans, TreeNode *root, int level) {
if (root == nullptr)
return;
// 初始化下一层的集合
if (level == ans.size()) {
vector<int> tmp;
ans.emplace_back(tmp);
}
// 把节点的值添加到对应的集合中
ans[level].push_back(root->val);
// 递归左右子树
dfs(ans, root->left, level + 1);
dfs(ans, root->right, level + 1);
}
};
void reverse(int **nums, int *column, int left, int right) {
while (left < right) {
int *tmp1 = nums[left]; // 答案数组交换
nums[left] = nums[right];
nums[right] = tmp1;
int tmp2 = column[left]; // 列数组交换
column[left] = column[right];
column[right] = tmp2;
left++;
right--;
}
}
void dfs(int **ans, struct TreeNode *root, int *returnSize, int *returnColumnSizes, int level) {
if (root == NULL)
return;
// 初始化下一层的集合
if (level == *returnSize)
ans[(*returnSize)++] = malloc(sizeof(int) * 2001);
// 把节点的值添加到对应的集合中
ans[level][(returnColumnSizes[level])++] = root->val;
// 递归左右子树
dfs(ans, root->left, returnSize, returnColumnSizes, level + 1);
dfs(ans, root->right, returnSize, returnColumnSizes, level + 1);
}
int **levelOrderBottom(struct TreeNode *root, int *returnSize, int **returnColumnSizes) {
int **ans = malloc(sizeof(int *) * 2001);
*returnSize = 0;
*returnColumnSizes = malloc(sizeof(int) * 2001);
memset(*returnColumnSizes, 0, sizeof(int) * 2001);
dfs(ans, root, returnSize, *returnColumnSizes, 0);
reverse(ans, *returnColumnSizes, 0, *returnSize - 1); // 反转
return ans;
}
def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
def dfs(tree: TreeNode, level: int):
if tree is None:
return
# 初始化下一层的集合
if level == len(ans):
ans.append([])
# 这里就相当于从后往前打印了
ans[level].append(tree.val)
# 递归左右子树
dfs(tree.left, level + 1)
dfs(tree.right, level + 1)
ans = []
dfs(root, 0)
return ans[::-1] # 结果反转