扫码关注微信公众号
回复“面试手册”,获取本站PDF版
回复“简历”,获取高质量简历模板
回复“加群”,加入程序员交流群
回复“电子书”,获取程序员类电子书
题目描述
从上到下按层打印二叉树,同一层的节点按从左到右的顺序打印,每一层打印到一行。
例如: 给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果:
[
[3],
[9,20],
[15,7]
]
提示:
- 节点总数 <= 1000
算法
(BFS,层序遍历) O(n)
使用宽度优先搜索配合队列层序遍历二叉树
- 首先先将根节点入队列
- 如果队列不为空,进行以下循环
- 计算当前队列中的元素个数 sz,即当前层的元素个数
- 遍历当前层的每个元素,每次弹出队头元素,并将其对应的值加入到当前层序列中,如果当前节点有左孩子,则将左孩子入队列,如果当前节点有右孩子,则将右孩子入队列,代表下一层节点。
- 遍历完一层将当前层序列添加到答案中。
时间复杂度
二叉树的每个节点只会被遍历一次,所以时间复杂度为 O(n)。
空间复杂度
存储答案需要额外 O(n^2) 的空间,队列需要额外 O(n) 的空间。
C++ 代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> ans;
queue<TreeNode*> q;
if (root) q.push(root);
while (q.size()) {
int sz = q.size();
vector<int> line;
while (sz -- ) {
auto t = q.front();
q.pop();
line.push_back(t->val);
if (t->left) q.push(t->left);
if (t->right) q.push(t->right);
}
ans.push_back(line);
}
return ans;
}
};
Java 代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
Queue<TreeNode> q = new LinkedList<>();
if (root != null) {
q.offer(root);
}
while (!q.isEmpty()) {
int sz = q.size();
List<Integer> line = new ArrayList<>();
while (sz -- > 0) {
TreeNode t = q.poll();
line.add(t.val);
if (t.left != null) {
q.offer(t.left);
}
if (t.right != null) {
q.offer(t.right);
}
}
ans.add(line);
}
return ans;
}
}
Python 代码
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
ans = []
q = deque()
if root:
q.append(root)
while q:
sz = len(q)
line = []
while sz > 0:
t = q.popleft()
line.append(t.val)
if t.left:
q.append(t.left)
if t.right:
q.append(t.right)
sz -= 1
ans.append(line)
return ans
本文由读者提供,Github地址:https://github.com/tonngw
点击面试手册,获取本站面试手册PDF完整版