LeetCode刷题实战102:二叉树的层序遍历
共 2308字,需浏览 5分钟
·
2020-11-23 21:27
算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !
今天和大家聊的问题叫做 二叉树的层序遍历,我们先来看题面:
https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
题意
解题
class Solution {
public List<List> levelOrder(TreeNode root) {
List<List> res = new ArrayList<>();
Queueq = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
int size = q.size();
Listlevel = new LinkedList<>();
for (int i = 0; i < size; ++i) {
TreeNode cur = q.peek();
q.poll();
if (cur == null) {
continue;
}
level.add(cur.val);
q.offer(cur.left);
q.offer(cur.right);
}
if (!level.isEmpty()) {
res.add(level);
}
}
return res;
}
}
class Solution {
public List<List> levelOrder(TreeNode root) {
List<List> res = new ArrayList<>();
if(root != null){
dfs(res, root, 0);
}
return res;
}
private void dfs(List<List> res, TreeNode node, int level){
if(res.size() - 1 < level){
res.add(new ArrayList());
}
res.get(level).add(node.val);
if(node.left!=null){
dfs(res, node.left, level + 1);
}
if(node.right!=null){
dfs(res, node.right, level + 1);
}
}
}
上期推文: