这题让对二叉树进行层序遍历，实际上就是二叉树的 BFS （宽度优先搜索，也叫广度优先搜索）遍历，需要使用一个队列，来记录每层的节点，遍历当前节点之后，需要把它的两个子节点（如果不为空）添加到队列中，每层都需要创建一个集合，每层的节点需要放到对应的集合中。
怎么确定每层有多少节点呢？实际上在每层遍历开始之前就要先记录下该层的节点个数，步骤如下图所示：
public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
if (root == null)
return ans;
Queue<TreeNode> q = new LinkedList<>();// 创建队列
q.offer(root);// 把根节点添加到队列中
while (!q.isEmpty()) {
int cnt = q.size();// 每层的节点个数
// 记录当前层的节点值
ArrayList<Integer> subList = new ArrayList<>();
// 遍历当前层的所有节点，顺便把下一层的所有节点添加到队列中。
for (int i = 0; i < cnt; i++) {
TreeNode cur = q.poll();// 节点出队
subList.add(cur.val);// 添加节点到集合中。
// 左右子节点如果不为空就添加到队列中。
if (cur.left != null)
q.offer(cur.left);
if (cur.right != null)
q.offer(cur.right);
}
ans.add(subList);
}
return ans;
}
public:
vector<vector<int>> levelOrder(TreeNode *pRoot) {
vector<vector<int>> ans;
if (pRoot == nullptr)
return ans;
queue<TreeNode *> q;// 创建队列
q.push(pRoot);// 把根节点添加到队列中
while (!q.empty()) {
int cnt = q.size();// 每层的节点个数
// 记录当前层的节点值
vector<int> subList;
// 遍历当前层的所有节点，顺便把下一层的所有节点添加到队列中。
for (int i = 0; i < cnt; i++) {
TreeNode *cur = q.front();
q.pop();// 节点出队
subList.push_back(cur->val);// 添加节点到集合中。
// 左右子节点如果不为空就添加到队列中。
if (cur->left)
q.push(cur->left);
if (cur->right)
q.push(cur->right);
}
ans.push_back(subList);
}
return ans;
}
虽然这题要求的是层序遍历，但我们也可以使用 DFS 的方式来遍历，但需要使用一个参数 level 来记录当前节点在二叉树的第几层，因为每层都要创建一个集合，遍历的时候当前节点在第几层就添加到第几层的集合中。
public ArrayList<ArrayList<Integer>> levelOrder(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
dfs(ans, pRoot, 0);
return ans;
}
// level ：记录当前节点node是第几层。
private void dfs(ArrayList<ArrayList<Integer>> ans, TreeNode node, int level) {
if (node == null) return;
// 第一次到达第level层，需要创建该层的集合。
if (level >= ans.size()) ans.add(new ArrayList<>());
ans.get(level).add(node.val);// 把节点node的值添加到对应的集合中。
dfs(ans, node.left, level + 1);// 递归左子节点
dfs(ans, node.right, level + 1);// 递归右子节点
}
public:
vector<vector<int>> levelOrder(TreeNode *pRoot) {
vector<vector<int>> ans;
dfs(ans, pRoot, 0);
return ans;
}
// level ：记录当前节点node是第几层。
void dfs(vector<vector<int>> &ans, TreeNode *node, int level) {
if (node == nullptr) return;
// 第一次到达第level层，需要创建该层的集合。
if (level >= ans.size())
ans.emplace_back();
ans[level].push_back(node->val);// 把节点node的值添加到对应的集合中。
dfs(ans, node->left, level + 1);// 递归左子节点
dfs(ans, node->right, level + 1);// 递归右子节点
}
京公网安备 11010502036488号