代码随想录二刷day15

news/2025/2/19 14:46:07/

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

  • 前言
  • 一、力扣102. 二叉树的层序遍历
  • 二、力扣107. 二叉树的层序遍历 II
  • 三、力扣199. 二叉树的右视图
  • 四、力扣637. 二叉树的层平均值
  • 五、力扣429. N 叉树的层序遍历
  • 六、力扣515. 在每个树行中找最大值
  • 七、力扣116. 填充每个节点的下一个右侧节点指针
  • 八、力扣117. 填充每个节点的下一个右侧节点指针 II
  • 九、力扣104. 二叉树的最大深度
  • 十、力扣111. 二叉树的最小深度
  • 十一、力扣226. 翻转二叉树
  • 十二、力扣101. 对称二叉树

前言

一、力扣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>> res = new ArrayList<>();Deque<TreeNode> deq = new ArrayDeque<>();List<Integer> li = new ArrayList<>();if(root == null)return res;deq.offerLast(root);TreeNode pre = root;while(!deq.isEmpty()){TreeNode p = deq.pollFirst();li.add(p.val);if(p.left != null)deq.offerLast(p.left);if(p.right != null)deq.offerLast(p.right);if(pre == p){res.add(li);li = new ArrayList();pre = deq.peekLast();}}return res;}
}

二、力扣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) {List<List<Integer>> res = new ArrayList<>();Deque<TreeNode> deq = new ArrayDeque<>();if(root == null)return res;deq.offerLast(root);while(!deq.isEmpty()){int len = deq.size();List<Integer> li = new ArrayList<>();for(int i = 0; i < len; i ++){TreeNode p = deq.pollFirst();li.add(p.val);if(p.left != null)deq.offerLast(p.left);if(p.right != null)deq.offerLast(p.right);}res.add(li);}   List<List<Integer>> r = new ArrayList<>(); for(int i = res.size()-1; i >= 0; i--){r.add(res.get(i));}return r;}
}

三、力扣199. 二叉树的右视图

/*** 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> res = new ArrayList<>();Deque<TreeNode> deq = new ArrayDeque<>();if(root == null)return res;deq.offerLast(root);while(!deq.isEmpty()){int len = deq.size();for(int i = 0; i < len; i ++){TreeNode p = deq.pollFirst();if(i == len - 1){res.add(p.val);}if(p.left != null)deq.offerLast(p.left);if(p.right != null)deq.offerLast(p.right);}}return res;}
}

四、力扣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> res = new ArrayList<>();Deque<TreeNode> deq = new ArrayDeque<>();deq.offerLast(root);while(!deq.isEmpty()){int len = deq.size();double count = 0;for(int i = 0; i < len; i ++){TreeNode p = deq.pollFirst();count += p.val;if(p.left != null)deq.offerLast(p.left);if(p.right != null)deq.offerLast(p.right);}res.add(count / len);}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) {List<List<Integer>> res = new ArrayList<>();Deque<Node> deq = new ArrayDeque<>();if(root == null)return res;deq.offerLast(root);while(!deq.isEmpty()){int len = deq.size();List<Integer> l = new ArrayList<>();for(int i = 0; i < len; i ++){Node p = deq.pollFirst();l.add(p.val);List<Node> li = p.children;for(Node n : li){if(n != null)deq.offerLast(n);}}res.add(l);}return res;}
}

六、力扣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> res = new ArrayList<>();Deque<TreeNode> deq = new ArrayDeque<>();if(root == null)return res;deq.offerLast(root);while(!deq.isEmpty()){int len = deq.size();int max = Integer.MIN_VALUE;for(int i = 0; i < len; i ++){TreeNode p = deq.pollFirst();max = max > p.val ? max:p.val;if(p.left != null)deq.offerLast(p.left);if(p.right != null)deq.offerLast(p.right);}res.add(max);}return res;}
}

七、力扣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> deq = new ArrayDeque<>();if(root == null)return root;deq.offerLast(root);while(!deq.isEmpty()){int len = deq.size();for(int i = 0; i < len; i ++){Node p = deq.pollFirst();if(i != len-1){Node ne = deq.peekFirst();p.next = ne;}if(p.left != null)deq.offerLast(p.left);if(p.right != null)deq.offerLast(p.right);}}return root;}
}

八、力扣117. 填充每个节点的下一个右侧节点指针 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> deq = new ArrayDeque<>();if(root == null)return root;deq.offerLast(root);while(!deq.isEmpty()){int len = deq.size();for(int i = 0; i < len; i ++){Node p = deq.pollFirst();if(i != len-1){Node ne = deq.peekFirst();p.next = ne;}if(p.left != null)deq.offerLast(p.left);if(p.right != null)deq.offerLast(p.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) {if(root == null){return 0;}int l = maxDepth(root.left);int r = maxDepth(root.right);return l > r ? l + 1: r + 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 int maxDepth(TreeNode root) {Deque<TreeNode> deq = new ArrayDeque<>();if(root == null)return 0;deq.offerLast(root);int high = 0;while(!deq.isEmpty()){int len = deq.size();for(int i = 0; i < len; i ++){TreeNode p = deq.pollFirst();if(p.left != null)deq.offerLast(p.left);if(p.right != null)deq.offerLast(p.right);}high ++;}return high;}
}

十、力扣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) {Deque<TreeNode> deq = new ArrayDeque<>();if(root == null)return 0;deq.offerLast(root);int high = 0;while(!deq.isEmpty()){int len = deq.size();for(int i = 0; i < len; i ++){TreeNode p = deq.pollFirst();if(p.left == null && p.right == null){return high + 1;}if(p.left != null)deq.offerLast(p.left);if(p.right != null)deq.offerLast(p.right);}high ++;}return high;}
}

十一、力扣226. 翻转二叉树

迭代

/*** 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 TreeNode invertTree(TreeNode root) {Deque<TreeNode> deq = new ArrayDeque<>();if(root == null)return root;deq.offerLast(root);while(!deq.isEmpty()){int len = deq.size();for(int i = 0; i < len; i ++){TreeNode p = deq.pollFirst();TreeNode temp = p.left;p.left = p.right;p.right = temp;if(p.left != null)deq.offerLast(p.left);if(p.right != null)deq.offerLast(p.right);}}return root;}
}

递归

/*** 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 TreeNode invertTree(TreeNode root) {if(root == null)return null;TreeNode chirlLeft = invertTree(root.left);TreeNode chirlRight = invertTree(root.right);TreeNode temp = chirlLeft;root.left = chirlRight;root.right = temp;return root;}
}

十二、力扣101. 对称二叉树

递归

/*** 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 boolean isSymmetric(TreeNode root) {Deque<TreeNode> deq = new ArrayDeque<>();if(root == null)return true;if(root.left == null && root.right == null)return true;if(root.left == null)return false;if(root.right == null)return false;if(root.left.val != root.right.val)return false;deq.offerLast(root.left);deq.offerLast(root.right);while(!deq.isEmpty()){int len = deq.size();if(len % 2 == 1)return false;TreeNode[] arr = new TreeNode[len];for(int i = 0; i < len; i ++){TreeNode p = deq.pollFirst();arr[i] = p;if(p.left != null)deq.offerLast(p.left);if(p.right != null)deq.offerLast(p.right);}for(int i = 0, j = len-1; i < j ; i ++, j --){if(arr[i].left == null && arr[j].right != null)return false;if(arr[i].left != null && arr[j].right == null)return false;if(arr[j].left == null && arr[i].right != null)return false;if(arr[j].left != null && arr[i].right == null)return false;if(arr[i].left != null && arr[j].right != null && arr[i].left.val != arr[j].right.val)return false;if(arr[j].left != null && arr[i].right != null && arr[j].left.val != arr[i].right.val)return false;}}return true;}
}

迭代版本二

/*** 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 boolean isSymmetric(TreeNode root) {Deque<TreeNode> deq = new LinkedList<>();if(root == null)return true;deq.offerLast(root.left);deq.offerLast(root.right);while(!deq.isEmpty()){TreeNode childLeft = deq.pollFirst();TreeNode childRight = deq.pollFirst();if(childLeft == null && childRight == null)continue;if(childLeft != null && childRight == null)return false;if(childLeft == null && childRight != null)return false;if(childLeft != null && childRight != null && childLeft.val != childRight.val)return false;deq.offerLast(childLeft.left);deq.offerLast(childRight.right);deq.offerLast(childLeft.right);deq.offerLast(childRight.left);}return true;}
}

递归

/*** 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 boolean isSymmetric(TreeNode root) {return compareTree(root.left, root.right);}public boolean compareTree(TreeNode childL, TreeNode childR){if(childL == null && childR != null)return false;if(childL != null && childR == null)return false;if(childL == null && childR == null)return true;if(childL.val != childR.val)return false;boolean boolL = compareTree(childL.left, childR.right);boolean boooR = compareTree(childL.right, childR.left);return boolL && boooR;}
}

http://www.ppmy.cn/news/1096055.html

相关文章

CRM软件系统能否监控手机的使用

CRM软件系统能否监控手机的使用

CRM可以监控手机吗&#xff1f;答案是不可以。CRM是一款帮助企业优化业务流程&#xff0c;提高销售效率的工具。例如Zoho CRM&#xff0c;最多也就是听一下销售的通话录音&#xff0c;却不可以监控手机&#xff0c;毕竟CRM不是一款监控软件。 CRM的主要作用有以下几点&#xf…
阅读更多...
WPS或EXCEL表格单元格下拉快捷选择项修改及设置方法

WPS或EXCEL表格单元格下拉快捷选择项修改及设置方法

WPS或新版本EXCEL的设置下拉选项的方法是.点击一个单元格,菜单上选择数据,下拉列表即可设置,双击文字可编辑 EXCEL 旧的版本不同,可能有不同方法 方法一, 1.在空白区域里面&#xff0c;准备好需要填入下拉菜单里面的内容。 2.选中一个需要添加下拉菜单的单元格&#xff0c;然后…
阅读更多...
Python中的日期和时间（一）datetime模块

Python中的日期和时间（一）datetime模块

Python处理时间的对象很多&#xff0c;常用的有time、datetime和calendar等。本文对常用的时间对象的使用进行学习。在开始学习具体的对象前&#xff0c;先学习几个计算机的时间概念。 UTC&#xff08;全球标准时间&#xff09;:是全球范围内计时的科学标准&#xff0c;它基于…
阅读更多...
Web jQuery—选择器、样式和效果

Web jQuery—选择器、样式和效果

jQuery 选择器、样式和效果 代码下载 jQuery 介绍 JavaScript库&#xff1a;即 library&#xff0c;是一个封装好的特定的集合&#xff08;方法和函数&#xff09;。从封装一大堆函数的角度理解库&#xff0c;就是在这个库中&#xff0c;封装了很多预先定义好的函数在里面&a…
阅读更多...
数据结构——二叉树线索化遍历(前中后序遍历)

数据结构——二叉树线索化遍历(前中后序遍历)

二叉树线索化 线索化概念&#xff1a; 为什么要转换为线索化 二叉树线索化是一种将普通二叉树转换为具有特殊线索&#xff08;指向前驱和后继节点&#xff09;的二叉树的过程。这种线索化的目的是为了提高对二叉树的遍历效率&#xff0c;特别是在不使用递归或栈的情况下进行遍历…
阅读更多...
Spring系列文章：Spring使用JdbcTemplate

Spring系列文章：Spring使用JdbcTemplate

一、简介 JdbcTemplate是Spring提供的⼀个JDBC模板类&#xff0c;是对JDBC的封装&#xff0c;简化JDBC代码。 当然&#xff0c;你也可以不⽤&#xff0c;可以让Spring集成其它的ORM框架&#xff0c;例如&#xff1a;MyBatis、Hibernate等。 第一步&#xff1a;引入依赖 <d…
阅读更多...
java 整合 swagger-ui 步骤

java 整合 swagger-ui 步骤

1.在xml 中添加Swagger 相关依赖 <!-- springfox-swagger2 --><dependency><groupId>io.springfox</groupId><artifactId>springfox-swagger2</artifactId><version>2.9.2</version></dependency><!-- springfox-swa…
阅读更多...
【excel密码】excel文件加密方法总结：

【excel密码】excel文件加密方法总结：

想要给Excel文件进行加密&#xff0c;方法有很多&#xff0c;今天分享三种Excel加密方法给大家。 打开密码 设置了打开密码的excel文件&#xff0c;打开文件就会提示输入密码才能打开excel文件&#xff0c;只有输入了正确的密码才能打开并且编辑文件&#xff0c;如果密码错误…
阅读更多...
最新文章

Copyright @ 2022~2023