102.二叉树的层序遍历
题目:102. 二叉树的层序遍历 - 力扣(LeetCode)
思路:同样用递归的方法?这个跟前、中、后序遍历有什么区别?
尝试
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new List<>();
preOrder(root,res);
return res;
}
public void preOrder(TreeNode root,List<List<Integer>> result){
if(root==null){
return;
}
result.add(root);
preOrder(root.left,result);
preOrder(root.right,result);
}
}
想不到其它思路,尝试用前序遍历,但是【List<List<Integer>>】的初始化写错了
答案
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> resList = new ArrayList<List<Integer>>();
if(root == null) return resList;
//队列是关键,每次要记住当前层的size,用于控制弹出元素的数量
Queue<TreeNode> que = new LinkedList<TreeNode>();
que.offer(root);
while (!que.isEmpty()) {
//临时的itemList记录的是弹出元素的值,也就是当前层所有节点的值
List<Integer> itemList = new ArrayList<Integer>();
//每次遍历,都要重新计算即将遍历的一层的元素数量,给while循环用
int len = que.size();
while (len > 0) {
TreeNode tmpNode = que.poll();
itemList.add(tmpNode.val);
if (tmpNode.left != null) que.offer(tmpNode.left);
if (tmpNode.right != null) que.offer(tmpNode.right);
len--;
}
resList.add(itemList);
}
return resList;
}
}
小结
🍉层序遍历这个概念我都没理解,意思是从上往下,每一层从左往右遍历过去来返回元素
🍉一个while循环控制层级下移,一个while循环遍历当前层元素
🍉用一个itemList记录每层的元素,之后要把itemList放入到resList里面
107.二叉树的层序遍历 II AC
题目:107. 二叉树的层序遍历 II - 力扣(LeetCode)
思路:先正常的层序遍历,存入resList里面,再转存到另一个list返回
尝试
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> resList = new ArrayList<List<Integer>>();
List<List<Integer>> tempList = new ArrayList<List<Integer>>();
if(root == null) return resList;
Queue<TreeNode> que = new LinkedList<TreeNode>();
que.offer(root);
while(!que.isEmpty()){
List<Integer> itemList = new ArrayList<>();
int len = que.size();
while(len>0){
TreeNode tempNode = que.poll();
itemList.add(tempNode.val);
if(tempNode.left != null) que.offer(tempNode.left);
if(tempNode.right != null) que.offer(tempNode.right);
len--;
}
tempList.add(itemList);
}
int n = tempList.size();
for(int i = n-1;i>=0;i--){
List<Integer> list = tempList.get(i);
resList.add(list);
}
return resList;
}
}
小结
🍉List是接口,ArrayList是对它的具体实现
199.二叉树的右视图 AC
题目:199. 二叉树的右视图 - 力扣(LeetCode)
思路:层序遍历时,只保留每一层最右边的元素,存起来返回出去
尝试
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<List<Integer>> tempList = new ArrayList<List<Integer>>();
List<Integer> resList = new ArrayList<Integer>();
if(root == null) return resList;
Queue<TreeNode> que = new LinkedList<TreeNode>();
que.offer(root);
while(!que.isEmpty()){
List<Integer> itemList = new ArrayList<Integer>();
int len = que.size();
int target = len - 1;
while(len>0){
TreeNode tmpNode = que.poll();
itemList.add(tmpNode.val);
if(tmpNode.left != null) que.offer(tmpNode.left);
if(tmpNode.right != null) que.offer(tmpNode.right);
len--;
}
resList.add(itemList.get(target));
}
return resList;
}
}
小结
🍉tmpNode存储的是队列里面弹出来的元素
637.二叉树的层平均值
题目:637. 二叉树的层平均值 - 力扣(LeetCode)
思路:层序遍历,计算平均值存储起来返回
尝试
答案
public List<Double> averageOfLevels(TreeNode root) {
List<Double> list = new ArrayList<>();
Deque<TreeNode> que = new LinkedList<>();
if (root == null) {
return list;
}
que.offerLast(root);
while (!que.isEmpty()) {
int levelSize = que.size();
double levelSum = 0.0;
for (int i = 0; i < levelSize; i++) {
TreeNode poll = que.pollFirst();
levelSum += poll.val;
if (poll.left != null) {
que.addLast(poll.left);
}
if (poll.right != null) {
que.addLast(poll.right);
}
}
list.add(levelSum / levelSize);
}
return list;
}
小结
🍉整数除整数,无法转换,所以先把sum定义为double类型,再求平均值
429.N叉树的层序遍历 AC
题目:429. N 叉树的层序遍历 - 力扣(LeetCode)
思路:感觉跟层序遍历是一个道理,逻辑上改一下就行
尝试
class Solution {
public List<List<Integer>> levelOrder(Node root) {
List<List<Integer>> tempList = new ArrayList<List<Integer>>();
if(root == null) return tempList;
Queue<Node> que = new LinkedList<Node>();
que.offer(root);
while(!que.isEmpty()){
List<Integer> itemList = new ArrayList<Integer>();
int len = que.size();
int target = len - 1;
while(len>0){
Node tmpNode = que.poll();
itemList.add(tmpNode.val);
for(Node node : tmpNode.children){
if(node!=null) que.add(node);
}
len--;
}
tempList.add(itemList);
}
return tempList;
}
}
515.在每个树行中找最大值
题目:515. 在每个树行中找最大值 - 力扣(LeetCode)
思路:层序遍历,每次存下最大值,可以直接用队列,每次存的时候把大的往前面存,忘了优先级队列怎么写,尬住了
答案
class Solution {
public List<Integer> largestValues(TreeNode root) {
if(root == null){
return Collections.emptyList();
}
List<Integer> result = new ArrayList();
Queue<TreeNode> queue = new LinkedList();
queue.offer(root);
while(!queue.isEmpty()){
int max = Integer.MIN_VALUE;
for(int i = queue.size(); i > 0; i--){
TreeNode node = queue.poll();
max = Math.max(max, node.val);
if(node.left != null) queue.offer(node.left);
if(node.right != null) queue.offer(node.right);
}
result.add(max);
}
return result;
}
}
小结
🍉在每一个队列中,直接用Math.max()函数去对比,不断更新最大值,最后存起来
🍉【Collections.emptyList()】直接返回空列表
116.填充每个节点的下一个右侧节点指针
题目:116. 填充每个节点的下一个右侧节点指针 - 力扣(LeetCode)
思路:层序遍历,每一层加上“#”,next可以在弹出的时候操作,不对,应该是队列里操作
我想的是,for循环每一层的元素,塞入到队列里面,然后弹出元素的next指向下一个弹出的元素,如果下一个弹出的元素为null,next就指向null,不会写,苦涩!
尝试
class Solution {
public Node connect(Node root) {
Node result = root;
if(root==null) return result;
List<List<Integer>> tempList = new ArrayList<List<Integer>>();
Queue<Node> que = new LinkedList<Node>();
que.offer(root);
while(!que.isEmpty()){
int len = que.size();
List<String> list = new ArrayList<String>();
while(len>0){
Node tempNode = que.poll();
list.add(tempNode.val);
if(tempNode.left!=null) que.offer(tempNode.left);
if(tempNode.right!=null) que.offer(tempNode.right);
len--;
}
for()
tempList.add("#");
tempList.add(list)
}
}
}
答案
只需要一个临时队列,每次记住队列的size,弹出时,更换 cur.next 和 cur
class Solution {
public Node connect(Node root) {
Queue<Node> tmpQueue = new LinkedList<Node>();
if (root != null) tmpQueue.add(root);
while (tmpQueue.size() != 0){
int size = tmpQueue.size();
Node cur = tmpQueue.poll();
if (cur.left != null) tmpQueue.add(cur.left);
if (cur.right != null) tmpQueue.add(cur.right);
for (int index = 1; index < size; index++){
Node next = tmpQueue.poll();
if (next.left != null) tmpQueue.add(next.left);
if (next.right != null) tmpQueue.add(next.right);
cur.next = next;
cur = next;
}
}
return root;
}
}
小结
🍉完全不用管 【#】
🍉注意读题!初始状态下,所有 next 指针都被设置为 NULL
。所以不需要你判断最后一个,只要你不处理就行,也就是index = 1
🍉的确是在弹出的过程中,把每个节点的next指向下一个弹出的元素
104.二叉树的最大深度
题目:104. 二叉树的最大深度 - 力扣(LeetCode)
思路:层序遍历,每次遍历之后计数加一
答案
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) return 0;
Queue<TreeNode> que = new LinkedList<>();
que.offer(root);
int depth = 0;
while (!que.isEmpty())
{
int len = que.size();
while (len > 0)
{
TreeNode node = que.poll();
if (node.left != null) que.offer(node.left);
if (node.right != null) que.offer(node.right);
len--;
}
depth++;
}
return depth;
}
}
111.二叉树的最小深度
题目:111. 二叉树的最小深度 - 力扣(LeetCode)
思路:层序遍历,判断上一层数量与下一层的关系,如果不是两倍,说明上一层就是最小深度所在层
尝试
class Solution {
public int minDepth(TreeNode root) {
Queue<TreeNode> que = new LinkedList<TreeNode>();
que.offer(root);
while(!que.isEmpty()){
List<Integer> list = new ArrayList<Integer>();
int len = que.size();
list.add(len);
while(len>0){
TreeNode tempNode = que.poll();
if(tempNode.left!=null) que.offer(tempNode.left);
if(tempNode.right!=null) que.offer(tempNode.right);
len--;
}
}
for(int i = 0;i < list.size() -1; i++){
if(list.get(i)*2!=list.get(i+1)){
return i;
}
}
}
}
答案
class Solution {
public int minDepth(TreeNode root){
if (root == null) {
return 0;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int depth = 0;
while (!queue.isEmpty()){
int size = queue.size();
depth++;
TreeNode cur = null;
for (int i = 0; i < size; i++) {
cur = queue.poll();
//如果当前节点的左右孩子都为空,直接返回最小深度
if (cur.left == null && cur.right == null){
return depth;
}
if (cur.left != null) queue.offer(cur.left);
if (cur.right != null) queue.offer(cur.right);
}
}
return depth;
}
}
小结
🍉每次遍历,记录深度,一旦这一层有节点左右孩子都为空,直接返回最小深度
226.翻转二叉树
思路:写一个函数,交换左右孩子
尝试
class Solution {
public TreeNode invertTree(TreeNode root) {
revertChildren(root);
return root;
}
public void revertChildren(TreeNode father){
if(father==null) return;
if(father.left==null && father.right==null) return;
TreeNode temp = father.right;
father.right = father.left;
father.left = temp;
if(father.right!=null){
revertChildren(father.left);
}
if(father.left!=null){
revertChildren(father.right);
}
return;
}
}
没有通过下面这个测试用例
kimi的解释:
你提供的代码实现中存在一个逻辑错误,导致它不能正确翻转整棵二叉树。问题在于你在交换左右子节点后,错误地递归调用了
revertChildren(father.left)
和revertChildren(father.right)
,而此时左右子节点已经被交换了,所以递归调用的顺序也应该是相反的。正确的递归逻辑应该是先递归翻转左子树,然后再递归翻转右子树。但是,由于你在交换左右子节点后,按照原来的顺序进行递归调用,实际上你并没有正确地翻转右子树。
答案
class Solution {
/**
* 前后序遍历都可以
* 中序不行,因为先左孩子交换孩子,再根交换孩子(做完后,右孩子已经变成了原来的左孩子),再右孩子交换孩子(此时其实是对原来的左孩子做交换)
*/
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
invertTree(root.left);
invertTree(root.right);
swapChildren(root);
return root;
}
private void swapChildren(TreeNode root) {
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
}
}
小结
🍉采用前序遍历或者是后序遍历
101.对称二叉树
思路:我直接层序遍历,每一层的存起来,再用双指针,两边向中间遍历,比较左右指针指向的元素是否相同,不同就返回false
尝试
class Solution {
public boolean isSymmetric(TreeNode root) {
List<List<Integer>> resList = new ArrayList<List<Integer>>();
if(root == null) return true;
Queue<TreeNode> que = new LinkedList<TreeNode>();
que.offer(root);
while(!que.isEmpty()){
List<Integer> itemList = new ArrayList<Integer>();
int len = que.size();
while(len>0){
TreeNode temp = que.poll();
itemList.add(temp.val);
if(temp.left != null) que.offer(temp.left);
if(temp.right != null) que.offer(temp.right);
len--;
}
resList.add(itemList);
}
for(List list : resList){
int n = list.size();
for(int i =0, j = n-1;i!=j;i++,j--){
if(list.get(i)!=list.get(j)) return false;
}
}
return true;
}
}
答案
public boolean isSymmetric1(TreeNode root) {
return compare(root.left, root.right);
}
private boolean compare(TreeNode left, TreeNode right) {
if (left == null && right != null) {
return false;
}
if (left != null && right == null) {
return false;
}
if (left == null && right == null) {
return true;
}
if (left.val != right.val) {
return false;
}
// 比较外侧
boolean compareOutside = compare(left.left, right.right);
// 比较内侧
boolean compareInside = compare(left.right, right.left);
return compareOutside && compareInside;
}
小结
🍉只能是后序,因为对称看的是左右,先要处理左右子节点,才能知道是否对称,才能向上一层返回信息