安徽网站建设推荐,网站网上商城建设,网站建设专家证书,搜索引擎不收录网站剑指 Offer 32 - II. 从上到下打印二叉树 II#xff08;java解题#xff09;1. 题目2. 解题思路3. 数据类型功能函数总结4. java代码5. 踩坑记录1. 题目
从上到下按层打印二叉树#xff0c;同一层的节点按从左到右的顺序打印#xff0c;每一层打印到一行。
例如: 给定二叉…
剑指 Offer 32 - II. 从上到下打印二叉树 IIjava解题1. 题目2. 解题思路3. 数据类型功能函数总结4. java代码5. 踩坑记录1. 题目
从上到下按层打印二叉树同一层的节点按从左到右的顺序打印每一层打印到一行。
例如: 给定二叉树: [3,9,20,null,null,15,7], 3/ \9 20/ \15 7返回其层次遍历结果
[[3],[9,20],[15,7]
]提示
节点总数 1000
作者Krahets 链接https://leetcode.cn/leetbook/read/illustration-of-algorithm/5vawr3/ 来源力扣LeetCode 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。
2. 解题思路
这一题和之前的剑指 Offer 32 - I一样还是用队列实现层次遍历。需要注意的是返回结果的数据结构变化。 问题的难点在于如何在队列进出的时候分清每一层的结点。 在实际的遍历过程中每一层的结点是集中出现的并且存在一个时间点队列中所有的结点都是属于一个队列的例如题中的树 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传
因此可以在如图所示的特殊时间点获取队列长度这也是当前层h的结点数将这些结点集中在一个循环中处理数值送入一个空列表中子树结点进栈。当这个循环结束之后第h层结点已经全部出队将该层结点的值列表存入结果队列中同时开启下一轮循环队列中记录第h1层的所有结点。
3. 数据类型功能函数总结
//LinkedList
LinkedListE listnamenew LinkedListE();//初始化
LinkedList.add(elment);//在链表尾部添加元素
LinkedList.removeFirst();//取出链表头部元素
LinkedList.size();//获取元素个数
//ArrayList
ArrayListE listnamenew ArrayListE();//初始化
ArrayList.add(elment);//在数组最后插入元素
ArrayList.stream().mapToInt(Integer::valueOf).toArray();//ArrayListInteger转为int[]
ArrayList.toArray();//Arraylist转为数组适用于String--char[]
//ListListInteger
ListListInteger namenew ArrayList();//或者是 new LinkedList()
//错误写法 ListListInteger namenew ListListInteger();4. java代码
class Solution {public ListListInteger levelOrder(TreeNode root) {ListListInteger resultnew ArrayList();//最后返回的结果LinkedListTreeNode queuenew LinkedListTreeNode();//队列if(rootnull){return result;}else{queue.add(root);while(queue.size()!0){int size queue.size();ArrayListInteger tempnew ArrayListInteger();while(size0){TreeNode nodequeue.removeFirst();temp.add(node.val);//添加左右子树if(node.left!null){queue.add(node.left);}if(node.right!null){queue.add(node.right);}size--;}result.add(temp);//temp.clear();}return result;}}
}5. 踩坑记录
一开始关于每一层节点值的统计写法如下
class Solution {public ListListInteger levelOrder(TreeNode root) {ListListInteger resultnew ArrayList();ArrayListInteger tempnew ArrayListInteger();//***列表定义写在此处而不是while循环中LinkedListTreeNode queuenew LinkedListTreeNode();if(rootnull){return result;}else{queue.add(root);while(queue.size()!0){int size queue.size();//ArrayListInteger tempnew ArrayListInteger();//*** while(size0){TreeNode nodequeue.removeFirst();temp.add(node.val);//添加左右子树if(node.left!null){queue.add(node.left);}if(node.right!null){queue.add(node.right);}size--;}result.add(temp);temp.clear();//***添加clear(),希望下次记录之前将列表清空}return result;}}
}这样写忽略了实际上list.add()是进行浅拷贝的也就是说如果使用一个列表元素每次清空的话实际上每层的结果都指向同一个内存地址后续在此内存地址上的操作将会改变前期的结果。最终出现[[x,y,z][x,y,z][x,y,z]]三个子列表相同的情况。 因此应该对每一层都创建一个列表元素从而保证每一层的列表修改不会相互影响。
