精品推荐：
《征服数据结构》专栏：50多种数据结构彻底征服
《经典图论算法》专栏：50多种经典图论算法全部掌握
最近京东也开奖了，为了招人真的是下猛药了，年薪高达70万，京东今年给的确实挺高。之前美团开奖的时候我以为美团给的已经很高的了，结果和京东一对比简直不值一提。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第107题：二叉树的层序遍历 II。
问题描述
输入：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);
}
};
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] # 结果反转
数组，稀疏表(Sparse Table)，单向链表，双向链表，块状链表，跳表，队列和循环队列，双端队列，单调队列，栈，单调栈，双端栈，散列表，堆，字典树(Trie树)，ArrayMap，SparseArray，二叉树，二叉搜索树(BST)，笛卡尔树，AVL树，树堆(Treap)，FHQ-Treap，哈夫曼树，滚动数组，差分数组，LRU缓存，LFU缓存
……
图的介绍，图的表示方式，邻接矩阵转换，广度优先搜索(BFS)，深度优先搜索(DFS)，A*搜索算法，迭代深化深度优先搜索(IDDFS)，IDA*算法，双向广度优先搜索，迪杰斯特拉算法(Dijkstra)，贝尔曼-福特算法(Bellman-Ford)，SPFA算法，弗洛伊德算法(Floyd)，卡恩(Kahn)算法，基于DFS的拓扑排序，约翰逊算法(Johnson)
……
