# 题目
给你二叉树的根节点 root
,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。
示例 1:
输入:root = [1]
输出:[[1]]
示例 2:
输入:root = []
输出:[]
提示:
- 树中节点数目在范围
[0, 2000]
内 -1000 <= Node.val <= 1000
102. 二叉树的层序遍历 - 力扣(LeetCode)
# 分析
层序遍历其实就是广度优先遍历,队列先进先出,符合一层一层遍历的逻辑,而栈先进后出符合深度优先遍历的逻辑
class Solution { | |
public: | |
vector<vector<int>> levelOrder(TreeNode* root) { | |
queue<TreeNode*> que; | |
if (root != NULL) que.push(root); | |
vector<vector<int>> result; | |
while (!que.empty()) { | |
int size = que.size(); | |
vector<int> vec; | |
// 这里一定要使用固定大小 size,不要使用 que.size (),因为 que.size 是不断变化的 | |
for (int i = 0; i < size; i++) { | |
TreeNode* node = que.front(); | |
que.pop(); | |
vec.push_back(node->val); | |
if (node->left) que.push(node->left); | |
if (node->right) que.push(node->right); | |
} | |
result.push_back(vec); | |
} | |
return result; | |
} | |
}; |
递归实现
class Solution { | |
public: | |
void order(TreeNode* cur, vector<vector<int>>& result, int depth) | |
{ | |
if (cur == nullptr) return; | |
if (result.size() == depth) result.push_back(vector<int>()); | |
result[depth].push_back(cur->val); | |
order(cur->left, result, depth + 1); | |
order(cur->right, result, depth + 1); | |
} | |
vector<vector<int>> levelOrder(TreeNode* root) { | |
vector<vector<int>> result; | |
int depth = 0; | |
order(root, result, depth); | |
return result; | |
} | |
}; |