【二叉树层序遍历】【队列】Leetcode 102 107 199 637 429 515 116 117 104 111

2024-02-16 20:04
文章标签 leetcode 二叉树 遍历 层序 队列 111 117 104 107 102 429 515 199 116 637

本文主要是介绍【二叉树层序遍历】【队列】Leetcode 102 107 199 637 429 515 116 117 104 111，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【二叉树层序遍历】【队列】Leetcode 102 107 199 637 429 515 116 117

    • 102. 二叉树的层序遍历解法 用队列实现
    • 107. 二叉树的层序遍历 II解法
    • 199. 二叉树的右视图 解法
    • 637. 二叉树的层平均值 解法
    • 429. N叉树的层序遍历
    • 515. 在每个树行中找最大值
    • 116. 填充每个节点的下一个右侧节点指针
    • 117. 填充每个节点的下一个右侧节点指针 II
    • 104. 二叉树的最大深度
    • 111. 二叉树的最小深度

---------------🎈🎈102. 二叉树的层序遍历 题目链接🎈🎈-------------------
---------------🎈🎈107. 二叉树的层序遍历 II 题目链接🎈🎈-------------------

---------------🎈🎈199. 二叉树的右视图 题目链接🎈🎈-------------------
---------------🎈🎈637. 二叉树的层平均值 题目链接🎈🎈-------------------
---------------🎈🎈429. N叉树的层序遍历 题目链接🎈🎈-------------------
---------------🎈🎈515. 在每个树行中找最大值 题目链接🎈🎈-------------------

---------------🎈🎈116. 填充每个节点的下一个右侧节点指针 题目链接🎈🎈-------------------
---------------🎈🎈117. 填充每个节点的下一个右侧节点指针 II 题目链接🎈🎈-------------------

---------------🎈🎈104. 二叉树的最大深度 题目链接🎈🎈-------------------
---------------🎈🎈111. 二叉树的最小深度 题目链接🎈🎈-------------------

102. 二叉树的层序遍历解法 用队列实现

在这里插入图片描述
在这里插入图片描述

时间复杂度O(N)
空间复杂度O(N)

import com.sun.source.tree.Tree;/*** 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;Queue<TreeNode> myqueue = new LinkedList<>();myqueue.add(root);while(!myqueue.isEmpty()){List<Integer> tempres = new ArrayList<>();int size = myqueue.size(); // 获取当前层的节点数for(int i = 0; i< size; i++){TreeNode temp = myqueue.poll();tempres.add(temp.val);if(temp.left != null){myqueue.add(temp.left);}if(temp.right != null){myqueue.add(temp.right);}}result.add(tempres);}return result;}
}

107. 二叉树的层序遍历 II解法

在这里插入图片描述

在基础的层序遍历的基础上增加一个Collections.reverse（）翻转输出即可

/*** 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>> result = new ArrayList<>();Queue<TreeNode> myqueue = new LinkedList<>();if(root==null) return result;myqueue.add(root);while(!myqueue.isEmpty()){List<Integer> resulttemp = new ArrayList<>();int size = myqueue.size(); for(int i = 0; i< size; i++){TreeNode temp = myqueue.poll();resulttemp.add(temp.val);if(temp.left != null) {myqueue.add(temp.left);}if(temp.right != null) {myqueue.add(temp.right);}}result.add(resulttemp);}Collections.reverse(result);return result;}
}

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> result = new ArrayList<>();Queue<TreeNode> myqueue = new LinkedList<>();if(root == null) return result;myqueue.add(root);while(!myqueue.isEmpty()){int size = myqueue.size();for(int i = 0; i<size; i++){TreeNode temp = myqueue.poll();if(temp.left!=null){myqueue.add(temp.left);}if(temp.right!= null){myqueue.add(temp.right);}if(i == size-1){result.add(temp.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<>();Queue<TreeNode> myqueue = new LinkedList<>();if(root == null) return result;myqueue.add(root);while(!myqueue.isEmpty()){int size = myqueue.size(); //得到size：当前层节点数double sum = 0;for(int i = 0; i<size; i++){ //弹出并得到size个节点的平均值，并将下一层的节点加入到队列TreeNode temp = myqueue.poll();sum += temp.val;if(temp.left != null){myqueue.add(temp.left);}if(temp.right != null){myqueue.add(temp.right);}}result.add(sum/size);}return result;}
}

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>> result = new ArrayList<>();Queue<Node> myqueue = new LinkedList<>();if(root == null) return result;myqueue.add(root);while(!myqueue.isEmpty()){int size = myqueue.size();List<Integer> restemp = new ArrayList<>();for(int i = 0; i < size; i++){Node temp = myqueue.poll();restemp.add(temp.val); // 将值temp.val加入restempfor(Node node:temp.children){ // 遍历temp.chirdren 即为遍历每一个temp的子节点，如果不为null就加入到列表中if(node != null){myqueue.add(node);}}}result.add(restemp);}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<>();Queue<TreeNode> myqueue = new LinkedList<>();if(root == null) return result;myqueue.add(root);while(!myqueue.isEmpty()){int size = myqueue.size();int max = (int)Math.pow(-2, 31);for(int i = 0; i < size; i++){TreeNode temp = myqueue.poll();if(temp.left != null){myqueue.add(temp.left);}if(temp.right != null){myqueue.add(temp.right);}if(max < temp.val){max = temp.val;}}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) {Queue<Node> myqueue = new LinkedList<>();if(root == null) return root;myqueue.add(root);while(!myqueue.isEmpty()){int size = myqueue.size();Node head = myqueue.peek();for (int i = 0; i <size; i++) {Node temp = myqueue.poll();if(temp != head){head.next = temp;head = head.next;}if(temp.left != null){myqueue.add(temp.left);myqueue.add(temp.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) {Queue<Node> myqueue = new LinkedList<>();if(root == null) return root;myqueue.add(root);while(!myqueue.isEmpty()){int size = myqueue.size();Node head = myqueue.peek();for(int i = 0; i <size; i++){Node temp = myqueue.poll();if(temp != head){head.next = temp;head = head.next;}if(temp.left != null){myqueue.add(temp.left);}if(temp.right != null){myqueue.add(temp.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) {// 层序遍历Queue<TreeNode> myqueue = new LinkedList<>();if(root == null) return 0;myqueue.add(root);int result = 0;while(!myqueue.isEmpty()){int size = myqueue.size();for(int i = 0; i < size; i++){TreeNode temp = myqueue.poll();if(temp.left != null){myqueue.add(temp.left);}if(temp.right != null){myqueue.add(temp.right);}}result +=1;}return result;}
}

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) {// 层序遍历Queue<TreeNode> myqueue = new LinkedList<>();if(root == null) return 0;myqueue.add(root);int result = 0;while(!myqueue.isEmpty()){int size = myqueue.size();for(int i = 0; i < size; i++){TreeNode temp = myqueue.poll();if(temp.left != null){myqueue.add(temp.left);}if(temp.right != null){myqueue.add(temp.right);}if(temp.left == null && temp.right==null){return result+1;}}result +=1;}return result;}
}

这篇关于【二叉树层序遍历】【队列】Leetcode 102 107 199 637 429 515 116 117 104 111的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/715570。

相关文章

MySQL存储过程之循环遍历查询的结果集详解

MySQL存储过程之循环遍历查询的结果集详解

《MySQL存储过程之循环遍历查询的结果集详解》：本文主要介绍MySQL存储过程之循环遍历查询的结果集,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录前言1. 表结构2. 存储过程3. 关于存储过程的SQL补充总结前言近来碰到这样一个问题：在生产上导入的数据发现
阅读更多...
Java中常见队列举例详解(非线程安全)

Java中常见队列举例详解(非线程安全)

《Java中常见队列举例详解(非线程安全)》队列用于模拟队列这种数据结构,队列通常是指先进先出的容器,：本文主要介绍Java中常见队列(非线程安全)的相关资料,文中通过代码介绍的非常详细,需要的朋... 目录一.队列定义 二.常见接口 三.常见实现类3.1 ArrayDeque3.1.1 实现原理3.1.2
阅读更多...
C++ RabbitMq消息队列组件详解

C++ RabbitMq消息队列组件详解

《C++RabbitMq消息队列组件详解》：本文主要介绍C++RabbitMq消息队列组件的相关知识,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1. RabbitMq介绍2. 安装RabbitMQ3. 安装 RabbitMQ 的 C++客户端库4. A
阅读更多...
golang实现延迟队列(delay queue)的两种实现

golang实现延迟队列(delay queue)的两种实现

《golang实现延迟队列(delayqueue)的两种实现》本文主要介绍了golang实现延迟队列(delayqueue)的两种实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的... 目录1 延迟队列：邮件提醒、订单自动取消2 实现2.1 simplChina编程e简单版：go自带的time
阅读更多...
python进行while遍历的常见错误解析

python进行while遍历的常见错误解析

《python进行while遍历的常见错误解析》在Python中选择合适的遍历方式需要综合考虑可读性、性能和具体需求,本文就来和大家讲解一下python中while遍历常见错误以及所有遍历方法的优缺点... 目录一、超出数组范围问题分析错误复现解决方法关键区别二、continue使用问题分析正确写法关键点三
阅读更多...
JSR-107缓存规范介绍

JSR-107缓存规范介绍

《JSR-107缓存规范介绍》JSR是JavaSpecificationRequests的缩写,意思是Java规范提案,下面给大家介绍JSR-107缓存规范的相关知识,感兴趣的朋友一起看看吧... 目录1.什么是jsR-1072.应用调用缓存图示3.JSR-107规范使用4.Spring 缓存机制缓存是每一
阅读更多...
Java遍历HashMap的6种常见方式

Java遍历HashMap的6种常见方式

《Java遍历HashMap的6种常见方式》这篇文章主要给大家介绍了关于Java遍历HashMap的6种常见方式,方法包括使用keySet()、entrySet()、forEach()、迭代器以及分别... 目录1，使用 keySet() 遍历键，再通过键获取值2，使用 entrySet() 遍历键值对3，
阅读更多...
Java的栈与队列实现代码解析

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念（Stack）栈的实现代码队列（Queue）模拟实现队列(双链表实现)循环队列（循环数组
阅读更多...
Redis消息队列实现异步秒杀功能

Redis消息队列实现异步秒杀功能

《Redis消息队列实现异步秒杀功能》在高并发场景下,为了提高秒杀业务的性能,可将部分工作交给Redis处理,并通过异步方式执行,Redis提供了多种数据结构来实现消息队列,总结三种,本文详细介绍Re... 目录1 Redis消息队列1.1 List 结构1.2 Pub/Sub 模式1.3 Stream 结
阅读更多...
SpringKafka错误处理(重试机制与死信队列)

SpringKafka错误处理(重试机制与死信队列)

《SpringKafka错误处理(重试机制与死信队列)》SpringKafka提供了全面的错误处理机制,通过灵活的重试策略和死信队列处理,下面就来介绍一下,具有一定的参考价值,感兴趣的可以了解一下... 目录引言一、Spring Kafka错误处理基础二、配置重试机制三、死信队列实现四、特定异常的处理策略五
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2