算法训练day15 | 102. 二叉树的层序遍历及其各种拓展-爱代码爱编程
算法训练Day15 | 102. 二叉树的层序遍历、107.二叉树的层次遍历 II、199. 二叉树的右视图、637. 二叉树的层平均值、429.N叉树的层序遍历......
我新建的个人博客，欢迎访问：hmilzy.github.io
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) {
List<List<Integer>> result = new ArrayList<>();
if(root == null) {
return result;
}
Deque<TreeNode> deque = new LinkedList<>();
deque.offer(root);
while(!deque.isEmpty()) {
int size = deque.size();
List<Integer> list = new ArrayList<>();
for(int i = 0; i < size; i++) {
TreeNode cur = deque.poll();
list.add(cur.val);
if(cur.left != null) {
deque.offer(cur.left);
}
if(cur.right != null) {
deque.offer(cur.right);
}
}
result.add(list);
}
return result;
}
}
107.二叉树的层次遍历 II
题目链接：二叉树的层次遍历 II
要求是从底层往上存。
第一种思路就是按照原来的顺序，最后再把结果翻转即可
第二种思路就是仍然循环插入，但是每次直接把list插在头部就行了
在这里我想使用一下第二种方法，所以原先的List就用不了了，可以用Linkelist
/**
* 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;
}
Deque<TreeNode> deque = new LinkedList<>();
deque.offer(root);
while(!deque.isEmpty()) {
int size = deque.size();
List<Integer> list = new ArrayList<>();
for(int i = 0; i < size; i++) {
TreeNode cur = deque.poll();
list.add(cur.val);
if(cur.left != null) {
deque.add(cur.left);
}
if(cur.right != null) {
deque.add(cur.right);
}
}
result.addFirst(list);
}
return result;
}
}
199. 二叉树的右视图
题目链接：二叉树的右视图
当遍历到某一层的最后一个结点，就把它的值取出来放进result。
如何判断到了最后一个结点呢。就是当每一层循环到i == size -1 时。
/**
* 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> rightSideView(TreeNode root) {
List<Integer> result = new ArrayList<>();
Deque<TreeNode> deque = new LinkedList<>();
if(root == null) {
return result;
}
deque.offer(root);
while(!deque.isEmpty()) {
int size = deque.size();
for(int i = 0; i < size; i++) {
TreeNode cur = deque.poll();
if(cur.left != null) {
deque.offer(cur.left);
}
if(cur.right != null) {
deque.offer(cur.right);
}
if(i == size - 1) {
result.add(cur.val);
}
}
}
return result;
}
}
637. 二叉树的层平均值
题目链接：二叉树的层平均值
/**
* 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<Double> averageOfLevels(TreeNode root) {
List<Double> result = new ArrayList<>();
Deque<TreeNode> deque = new LinkedList<>();
if(root == null) {
return result;
}
deque.offer(root);
while(!deque.isEmpty()) {
int size = deque.size();
double sum = 0;
for(int i = 0; i < size; i++) {
TreeNode cur = deque.poll();
sum += cur.val;
if(cur.left != null) {
deque.offer(cur.left);
}
if(cur.right != null) {
deque.offer(cur.right);
}
}
result.add(sum / size);
}
return result;
}
}
429.N叉树的层序遍历
题目链接：N叉树的层序遍历
二叉树层序遍历，左右结点放进deque
N叉数层序遍历，子节点集合list遍历一个一个放入deque
/*
// 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) {
List<List<Integer>> result = new ArrayList<>();
Deque<Node> deque = new LinkedList<>();
if(root == null) {
return result;
}
deque.offer(root);
while(!deque.isEmpty()) {
int size = deque.size();
List<Integer> list = new ArrayList<>();
for(int i = 0; i < size; i++) {
Node cur = deque.poll();
list.add(cur.val);
if(cur.children != null) {
for(Node node : cur.children) {
deque.add(node);
}
}
}
result.add(list);
}
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) {
List<Integer> result = new ArrayList<>();
Deque<TreeNode> deque = new LinkedList<>();
if(root == null) {
return result;
}
deque.offer(root);
while(!deque.isEmpty()) {
int size = deque.size();
int max = Integer.MIN_VALUE;
for(int i = 0; i < size; i++) {
TreeNode cur = deque.poll();
if(cur.val > max) {
max = Math.max(max,cur.val);
}
if(cur.left != null) {
deque.offer(cur.left);
}
if(cur.right != null) {
deque.offer(cur.right);
}
}
result.add(max);
}
return result;
}
}
116. 填充每个节点的下一个右侧节点指针
题目链接：填充每个节点的下一个右侧节点指针
/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node next;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, Node _left, Node _right, Node _next) {
val = _val;
left = _left;
right = _right;
next = _next;
}
};
*/
class Solution {
public Node connect(Node root) {
Deque<Node> deque = new LinkedList<>();
if(root != null) {
deque.offer(root);
}
while(!deque.isEmpty()) {
int size = deque.size();
for(int i = 0; i < size; i++) {
Node cur = deque.poll();
if(i == size - 1) {
cur.next =null;
}else {
cur.next = deque.peek();
}
if(cur.left != null) {
deque.offer(cur.left);
}
if(cur.right != null) {
deque.offer(cur.right);
}
}
}
return root;
}
}
117. 填充每个节点的下一个右侧节点指针 II
题目链接：填充每个节点的下一个右侧节点指针 II
和上道题一样的
/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node next;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, Node _left, Node _right, Node _next) {
val = _val;
left = _left;
right = _right;
next = _next;
}
};
*/
class Solution {
public Node connect(Node root) {
Deque<Node> deque = new LinkedList<>();
if(root != null) {
deque.offer(root);
}
while(!deque.isEmpty()) {
int size = deque.size();
for(int i = 0; i < size; i++) {
Node cur = deque.poll();
if(i < size - 1) {
cur.next = deque.peek();
}
if(cur.left != null) {
deque.offer(cur.left);
}
if(cur.right != null) {
deque.offer(cur.right);
}
}
}
return root;
}
}
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) {
Deque<TreeNode> deque = new LinkedList<>();
if(root != null) {
deque.offer(root);
}
int depth = 0;
while(!deque.isEmpty()) {
depth++;
int size = deque.size();
for(int i = 0; i < size; i++) {
TreeNode cur = deque.poll();
if(cur.left != null) {
deque.offer(cur.left);
}
if(cur.right != null) {
deque.offer(cur.right);
}
}
}
return depth;
}
}
111.二叉树的最小深度
题目链接：二叉树的最小深度
/**
* 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;
}
Deque<TreeNode> deque = new LinkedList<>();
deque.add(root);
int depth = 0;
while (!deque.isEmpty()) {
int size = deque.size();
depth++;
for (int i = 0; i < size; i++) {
TreeNode node = deque.poll();
if (node.left == null && node.right == null) {
// 是叶子结点，直接返回depth，因为从上往下遍历，所以该值就是最小值
return depth;
}
if (node.left != null) {
deque.add(node.left);
}
if (node.right != null) {
deque.add(node.right);
}
}
}
return depth;
}
}