好的网站建设价格,证书兼职的正规平台哪里有,为企业做网站建设优化小程序包年竞价,高端网站设计公司排名算法#xff1a;
这道题适合用迭代法#xff0c;层序遍历#xff1a;按层遍历#xff0c;每次把每层最左边的值保存、更新到result里面。
看看Java怎么实现层序遍历的#xff08;用队列#xff09;#xff1a;
/*** Definition for a binary tree node.* public clas…
算法
这道题适合用迭代法层序遍历按层遍历每次把每层最左边的值保存、更新到result里面。
看看Java怎么实现层序遍历的用队列
/*** 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 {//定义全局变量result// public ListListInteger result new ArrayListListInteger();public ListListInteger result new ArrayListListInteger();public ListListInteger levelOrder(TreeNode root) {chek(root);return result;}public void chek(TreeNode node) {if (node null) return;QueueTreeNode que new LinkedListTreeNode();//在 Java 中当调用类的构造函数时使用括号可以传递参数或指定初始化的大小。如果没有传递参数则会使用默认的构造函数。//虽然在这种情况下使用括号是可选的但建议使用括号以提高代码的可读性和一致性。此外如果将来需要在构造函数中传递参数或指定初始化大小添加括号将更加方便。//把node加入queque.offer(node);while(!que.isEmpty()){//itemlist用来存储每一层的节点ListInteger itemlist new ArrayListInteger();//len表示每一层的节点数量int len que.size();while (len0){TreeNode tempt que.poll();itemlist.add(tempt.val);if (tempt.left ! null) que.offer(tempt.left);if (tempt.right ! null) que.offer(tempt.right);len--;}result.add(itemlist);}}
}
注意
Java里面有全局变量
即所有函数都可以用的变量比如result 写函数还有定义变量时要拼写正确并区分大小写
比如isEmpty,ArrayList等 Java定义变量
数据类型 变量名 初始值;
数据类型表示变量的数据类型例如int、double、String等。变量名表示变量的名称由字母、数字和下划线组成不能以数字开头且不能使用Java的关键字作为变量名。初始值表示变量的初始值可以是一个具体的数值、表达式或者其他变量的值。如果不需要初始值可以将其省略。
比如ListInteger itemList new ArrayListInteger();
其中ListInteger表示列表的数据类型整数类型的列表itemList是变量的名称new ArrayListInteger()是初始值创建了一个ArrayList类型的对象并将其赋值给itemList变量。
ArrayList和LinkedList的区别
ArrayList:
内部实现ArrayList是基于数组的实现。它使用动态数组来存储元素并可以根据需要自动调整容量。当元素数量超过当前容量时ArrayList会自动增加容量以便能够容纳更多的元素。随机访问由于ArrayList基于数组因此支持快速的随机访问。可以通过索引直接访问元素时间复杂度为O(1)。插入和删除在中间位置插入或删除元素时需要将后续元素进行移动因此时间复杂度为O(n)。但在末尾进行插入和删除操作时时间复杂度为O(1)。内存占用由于ArrayList使用连续的内存块来存储元素因此在存储大量元素时可能会导致内存碎片问题。
LinkedList:
内部实现LinkedList是基于链表的实现。它使用双向链表来存储元素每个节点包含对前一个节点和后一个节点的引用。随机访问由于LinkedList是基于链表的因此不支持快速的随机访问。要访问特定索引的元素需要从头节点或尾节点开始遍历链表时间复杂度为O(n)。插入和删除在中间位置插入或删除元素时只需要修改节点的引用时间复杂度为O(1)。但在末尾进行插入和删除操作时需要先遍历到末尾节点时间复杂度为O(n)。内存占用由于LinkedList使用链表存储元素每个节点需要额外的内存空间来保存前后节点的引用因此在存储大量元素时可能会占用更多的内存。
add和offer的区别
在 Java 中add 和 offer 是用于向队列Queue添加元素的方法它们有一些区别 返回值add 方法在成功添加元素后会返回 true如果无法添加元素例如队列已满则会抛出异常IllegalStateException 或其子类。而 offer 方法在成功添加元素后会返回 true如果无法添加元素例如队列已满则会返回 false。 异常处理add 方法在无法添加元素时会抛出异常而 offer 方法在无法添加元素时则会返回 false不会抛出异常。这使得在使用 offer 方法时可以通过返回值来判断元素是否成功添加而无需使用异常处理机制。 接口支持add 方法定义在 Collection 接口中而 offer 方法定义在 Queue 接口中。由于 Queue 是 Collection 的子接口所以所有实现了 Queue 接口的类都会包含 offer 方法。而 add 方法在一些特定的队列实现中可能没有定义。
总的来说add 和 offer 方法在添加元素时的行为基本相同但在处理无法添加元素的情况时有所不同。如果需要处理无法添加元素的情况可以使用 offer 方法并根据返回值进行判断。如果希望抛出异常来处理无法添加元素的情况可以使用 add 方法。
使用层序遍历找树左下角的值
调试过程 原因当i等于len时表示已经遍历完当前层级的所有节点。此时tempnode就是空节点没有val。所以要把for循环条件改为ilen
正确代码
/*** 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 findBottomLeftValue(TreeNode root) {QueueTreeNode que new LinkedList();que.offer(root);int res 0;while (!que.isEmpty()){int len que.size();for (int i0; i len; i){TreeNode tempnode que.poll();if (i 0) res tempnode.val;if (tempnode.left ! null) que.add(tempnode.left);if (tempnode.right ! null) que.add(tempnode.right);} }return res;}
}时间空间复杂度
在这段代码中使用了广度优先搜索BFS来遍历二叉树的每一层节点因此时间复杂度为O(N)其中N是二叉树中的节点数。
空间复杂度方面使用了一个队列que来存储节点最坏情况下队列的大小可以达到二叉树的最大宽度因此空间复杂度为O(W)其中W是二叉树的最大宽度。 综上所述时间复杂度为O(N)空间复杂度为O(W)。
