层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。
队列先进先出，符合一层一层遍历的逻辑，而是用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。
102. 二叉树的层序遍历
一旦出现层次遍历我们都可以使用队列作为辅助结构
迭代实现:
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/class Solution {public List<List<Integer>> levelOrder(TreeNode root) {//存放结果集LinkedList<List<Integer>> result = new LinkedList<>();if(root == null){return result;}//使用BFS//用一个队列存放元素Queue<TreeNode> q = new LinkedList<>();q.offer(root);// while 循环控制从上向下一层层遍历while (!q.isEmpty()){int size = q.size();//保存当前层的长度，然后处理当前层（十分重要，防止添加下层元素影响判断层中元素的个数）// 记录这一层的节点值List<Integer> level = new LinkedList<>();// for 循环控制每一层从左向右遍历for (int i = 0; i < size; i++) {//临时节点暂存元素 弹出原值防止重复计算TreeNode temp = q.poll();//将这一层元素通过for循环逐个加进去level.add(temp.val);if (temp.left != null){q.offer(temp.left);//将左孩子加入队列,左右孩子加入队列也就能让我们继续遍历下一层,如果==null说明遍历到最后一层了}if(temp.right != null){q.offer(temp.right);//将右孩子加入队列}}result.add(level);//将这一层的元素追加到结果集}return result;}}
107. 二叉树的层序遍历 II
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
//存放结果集
LinkedList<List<Integer>> result = new LinkedList<>();
if(root == null){
return result;
}
//使用DFS
//用一个队列存放元素
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
// while 循环控制从上向下一层层遍历
while (!q.isEmpty()){
int size = q.size();//保存当前层的长度，然后处理当前层（十分重要，防止添加下层元素影响判断层中元素的个数）
// 记录这一层的节点值
List<Integer> level = new LinkedList<>();
// for 循环控制每一层从左向右遍历
for (int i = 0; i < size; i++) {
//临时节点暂存元素 弹出原值防止重复计算
TreeNode temp = q.poll();
//将这一层元素通过for循环逐个加进去
level.add(temp.val);
if (temp.left != null){
q.offer(temp.left);//将左孩子加入队列,左右孩子加入队列也就能让我们继续遍历下一层,如果==null说明遍历到最后一层了
}
if(temp.right != null){
q.offer(temp.right);////将右孩子加入队列
}
}
//result.add(level);//将这一层的元素追加到结果集
result.addFirst(level);
}
return result;
}
}
199. 二叉树的右视图
层序遍历的时候，判断是否遍历到单层的最后面的元素，如果是，就放进result数组中，随后返回result就可以了。
class Solution {
/* BFS 层序遍历解法 */
public List<Integer> rightSideView(TreeNode root) {
List<Integer> res = new LinkedList<>();
if (root == null) {
return res;
}
// BFS 层序遍历，计算右侧视图
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
// while 循环控制从上向下一层层遍历
while (!q.isEmpty()) {
int sz = q.size();
// 每一层头部就是最右侧的元素
TreeNode last = q.peek();
for (int i = 0; i < sz; i++) {
TreeNode cur = q.poll();
// 控制每一层从右向左遍历
if (cur.right != null) {
q.offer(cur.right);
}
if (cur.left != null) {
q.offer(cur.left);
}
}
// 每一层的最后一个节点就是二叉树的右侧视图
res.add(last.val);
}
return res;
}
/* DFS 递归遍历解法 */
List<Integer> res = new ArrayList<>();
// 记录递归的层数
int depth = 0;
public List<Integer> rightSideView_DFS(TreeNode root) {
traverse(root);
return res;
}
// 二叉树遍历函数
void traverse(TreeNode root) {
if (root == null) {
return;
}
// 前序遍历位置
depth++;
if (res.size() < depth) {
// 这一层还没有记录值
// 说明 root 就是右侧视图的第一个节点
res.add(root.val);
}
// 注意，这里反过来，先遍历右子树再遍历左子树
// 这样首先遍历的一定是右侧节点
traverse(root.right);
traverse(root.left);
// 后序遍历位置
depth--;
}
}
637. 二叉树的层平均值
本题就是层序遍历的时候把一层求个总和在取一个均值。
class Solution {
public List<Double> averageOfLevels(TreeNode root) {
List<Double> res = new LinkedList<>();
if (root == null) return res;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
int size = q.size();
// 记录当前层所有节点之和
double sum = 0.0;
for (int i = 0; i < size; i++) {
TreeNode cur = q.poll();
sum += cur.val;
if (cur.left != null) {
q.offer(cur.left);
}
if (cur.right != null) {
q.offer(cur.right);
}
}
// 记录当前行的平均值
res.add( sum / size);
}
return res;
}
}
429. N 叉树的层序遍历
使用队列保存每一层的所有节点，把队列里的所有节点出队列，然后把这些出去节点各自的子节点入队列。
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public List<List<Integer>> levelOrder(Node root) {
LinkedList<List<Integer>> result = new LinkedList<>();
if (root == null){
return result;
}
//队列
Deque<Node> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()){
int size = q.size();
//记录本层的元素
List<Integer> level = new LinkedList<>();
for (int i = 0; i < size; i++) {
Node poll = q.pollFirst();
level.add(poll.val);//添加第一个元素
List<Node> children = poll.children;//所有的孩子节点
if (children == null || children.size() == 0){
continue;//跳出这个循环
}
for (Node child : children) {
if (child != null){
q.offerLast(child);
}
}
}
result.add(level);//添加本层元素
}
return result;
}
}
小结 每一层的for循环都是为了遍历本层的所有元素,首先添加这层最左边的
level.add(poll.val);然后遍历添加后面的q.offerLast(child)
大神:
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public List<List<Integer>> levelOrder(Node root) {
LinkedList<List<Integer>> result = new LinkedList<>();
if (root == null){
return result;
}
//队列
Queue<Node> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()){
int size = q.size();
LinkedList<Integer> level = new LinkedList<>();
for (int i = 0; i < size; i++) {
Node poll = q.poll();
level.add(poll.val);
q.addAll(poll.children);
}
result.add(level);
}
return result;
}
}
515. 在每个树行中找最大值
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> largestValues(TreeNode root) {
LinkedList<Integer> result = new LinkedList<>();
if (root == null){
return result;
}
//queue
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()){
int size = q.size();
int max = Integer.MIN_VALUE;//记录当前层次的最大值
for (int i = 0; i < size; i++) {
TreeNode temp = q.poll();
if (temp.left != null){
q.offer(temp.left);
}
if (temp.right!= null){
q.offer(temp.right);
}
//前面的两个if相当于循环遍历我们这一层的每一个值每一次取出来的值是temp.val
if (max <= temp.val){
max = temp.val;
}
}
result.add(max);
}
return result;
}
}
116. 填充每个节点的下一个右侧节点指针
不会啊
class Solution {
public Node connect(Node root) {
if (root == null) {
return root;
}
// 初始化队列同时将第一层节点加入队列中，即根节点
Queue<Node> queue = new LinkedList<Node>();
queue.add(root);
// 外层的 while 循环迭代的是层数
while (!queue.isEmpty()) {
// 记录当前队列大小
int size = queue.size();
// 遍历这一层的所有节点
for (int i = 0; i < size; i++) {
// 从队首取出元素
Node node = queue.poll();
// 连接
if (i < size - 1) {
node.next = queue.peek();
}
// 拓展下一层节点
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
}
// 返回根节点
return root;
}
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node/solution/tian-chong-mei-ge-jie-dian-de-xia-yi-ge-you-ce-2-4/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
另一种思路:
你可以把二叉树的相邻节点抽象成一个「三叉树节点」，这样二叉树就变成了一棵「三叉树」，然后你去遍历这棵三叉树，把每个「三叉树节点」中的两个节点连接就行了：
class Solution {
// 主函数
public Node connect(Node root) {
if (root == null) return null;
// 遍历「三叉树」，连接相邻节点
traverse(root.left, root.right);
return root;
}
// 三叉树遍历框架
void traverse(Node node1, Node node2) {
if (node1 == null || node2 == null) {
return;
}
/**** 前序位置 ****/
// 将传入的两个节点穿起来
node1.next = node2;
// 连接相同父节点的两个子节点
traverse(node1.left, node1.right);
traverse(node2.left, node2.right);
// 连接跨越父节点的两个子节点
traverse(node1.right, node2.left);
}
}
// 详细解析参见：
// https://labuladong.gitee.io/article/?qno=116
104. 二叉树的最大深度
使用广度优先:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
int max = 0;
if (root == null) return max;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()){
int size = q.size();
//下面用for循环一样
while (size > 0){
TreeNode node = q.poll();
if (node.left != null) q.offer(node.left);
if (node.right != null) q.offer(node.right);
size--;
}
max++;
}
return max;
}
}
深度优先:
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
} else {
int leftHeight = maxDepth(root.left);
int rightHeight = maxDepth(root.right);
return Math.max(leftHeight, rightHeight) + 1;
}
}
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/solution/er-cha-shu-de-zui-da-shen-du-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
111. 二叉树的最小深度
DFS:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
} else if (root.left == null) {
return minDepth(root.right) + 1;
} else if (root.right == null) {
return minDepth(root.left) + 1;
} else {
return Math.min(minDepth(root.right), minDepth(root.left)) + 1;
}
}
}
BFS:
需要注意的是，只有当左右孩子都为空的时候，才说明遍历的最低点了。如果其中一个孩子为空则不是最低点
class Solution {
public int minDepth(TreeNode root) {
if (root == null) return 0;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
// root 本身就是一层，depth 初始化为 1
int depth = 1;
while (!q.isEmpty()) {
int sz = q.size();
/* 遍历当前层的节点 */
for (int i = 0; i < sz; i++) {
TreeNode cur = q.poll();
/* 判断是否到达叶子结点 */
if (cur.left == null && cur.right == null)
return depth;
/* 将下一层节点加入队列 */
if (cur.left != null)
q.offer(cur.left);
if (cur.right != null)
q.offer(cur.right);
}
/* 这里增加步数 */
depth++;
}
return depth;
}
}
// 详细解析参见：
// https://labuladong.gitee.io/article/?qno=111
若有收获，就点个赞吧
0 人点赞
