follow：代码随想录
107. 二叉树的层序遍历2⃣️
题目描述：
给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）。
解析：
一般的层序遍历是从上到下，而本题的层序遍历是从下到上，只需添加到链表表头即可！！
解答：
class Solution {
public List> levelOrderBottom(TreeNode root) {
List> result = new ArrayList<>();
Deque queue = new linkedList<>();
if(root != null){
queue.offerLast(root);
}
while(!queue.isEmpty()){
int len = queue.size();
List element = new ArrayList<>();
while(len > 0){
TreeNode temp = queue.removeFirst();
element.add(temp.val);
if(temp.left != null) queue.offerLast(temp.left);
if(temp.right != null) queue.offerLast(temp.right);
len--;
}
//在链表的指定位置添加元素
result.add(0, element);
}
return result;
}
}
199.二叉树的右视图
题目描述：
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
解析：
只需要在层次遍历时，遍历到最右侧时才添加到结果中
解答：
class Solution {
public List rightSideView(TreeNode root) {
List result = new ArrayList<>();
Deque queue = new linkedList<>();
if(root != null) queue.offerLast(root);
while(!queue.isEmpty()){
int len = queue.size();
while(len > 0){
TreeNode temp = queue.removeFirst();
if(temp.left != null) queue.offerLast(temp.left);
if(temp.right != null) queue.offerLast(temp.right);
if(--len == 0){
result.add(temp.val);
}
}
}
return result;
}
}
637 二叉树的平均值
题目描述：
给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。
解答：
class Solution {
public List averageOfLevels(TreeNode root) {
List result = new ArrayList<>();
Deque queue = new linkedList<>();
if(root != null) queue.offerLast(root);
while(!queue.isEmpty()){
int len = queue.size(), mem = queue.size();
//防溢出
long sum = 0;
while(len > 0){
TreeNode temp = queue.removeFirst();
sum += temp.val;
if(temp.left != null) queue.offerLast(temp.left);
if(temp.right != null) queue.offerLast(temp.right);
len--;
}
result.add((double)sum / mem);
}
return result;
}
}
429. N叉树的层序遍历
class Solution {
public List> levelOrder(Node root) {
List> result = new ArrayList<>();
Deque queue = new linkedList<>();
if(root != null) queue.offerLast(root);
while(!queue.isEmpty()){
int len = queue.size();
List element = new ArrayList<>();
while(len > 0){
Node temp = queue.removeFirst();
element.add(temp.val);
//可以使用集合中addAll()
if(temp.children != null) queue.addAll(temp.children);
len--;
}
result.add(element);
}
return result;
}
}
515 在每个树行中找最大值
class Solution {
public List largestValues(TreeNode root) {
List result = new ArrayList<>();
Deque queue = new linkedList<>();
if(root != null) queue.offerLast(root);
while(!queue.isEmpty()){
int len = queue.size();
int temp = Integer.MIN_VALUE;
while(len > 0){
TreeNode node = queue.removeFirst();
if(node.val > temp) temp = node.val;
if(node.left != null) queue.offerLast(node.left);
if(node.right != null) queue.offerLast(node.right);
len--;
}
result.add(temp);
}
return result;
}
}
116 填充每个节点的下一个右侧节点指针
题目描述：
给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
解答：
class Solution {
public Node connect(Node root) {
Deque queue = new linkedList<>();
if(root != null) queue.offerLast(root);
while(!queue.isEmpty()){
int len = queue.size();
Node prev = null;
while(len > 0){
Node temp = queue.removeFirst();
if(prev != null){
prev.next = temp;
}
prev = temp;
if(temp.left != null) queue.offerLast(temp.left);
if(temp.right != null) queue.offerLast(temp.right);
len--;
}
}
return root;
}
}
104二叉树的最大深度
解答：
迭代法：
class Solution {
public int maxDepth(TreeNode root) {
Deque queue = new linkedList<>();
if(root != null) queue.offerLast(root);
int maxdepth = 0;
while(!queue.isEmpty()){
int len = queue.size();
maxdepth++;
while(len > 0){
TreeNode temp = queue.removeFirst();
if(temp.left != null) queue.offerLast(temp.left);
if(temp.right != null) queue.offerLast(temp.right);
len--;
}
}
return maxdepth;
}
}
递归法：
class Solution {
public int maxDepth(TreeNode root) {
if(root == null) return 0;
return max_level(root);
}
public int max_level(TreeNode node){
if(node.left == null && node.right == null) return 1;
int temp_left = 0, temp_right = 0;
if(node.left != null) temp_left = max_level(node.left) + 1;
if(node.right != null) temp_right = max_level(node.right) + 1;
return Math.max(temp_left, temp_right);
}
}
111. 二叉树的最小深度
解答：
class Solution {
public int minDepth(TreeNode root) {
Deque queue = new linkedList<>();
if(root != null){
queue.offerLast(root);
}
int count = 0;
while(!queue.isEmpty()){
count++;
int len = queue.size();
while(len > 0){
TreeNode temp = queue.removeFirst();
if(temp.left == null && temp.right == null){
return count;
}
if(temp.left != null) queue.offerLast(temp.left);
if(temp.right != null) queue.offerLast(temp.right);
len--;
}
}
return count;
}
}
