网站地址查询最新区域名,如何写好网站文案,建设银行唐山分行网站,如何看网站是谁做的103. 二叉树的锯齿形层序遍历
给你二叉树的根节点 root #xff0c;返回其节点值的 锯齿形层序遍历 。#xff08;即先从左往右#xff0c;再从右往左进行下一层遍历#xff0c;以此类推#xff0c;层与层之间交替进行#xff09;。
示例 1#xff1a;输入#xff1a…103. 二叉树的锯齿形层序遍历
给你二叉树的根节点 root 返回其节点值的 锯齿形层序遍历 。即先从左往右再从右往左进行下一层遍历以此类推层与层之间交替进行。
示例 1输入root [3,9,20,null,null,15,7]
输出[[3],[20,9],[15,7]]示例 2输入root [1]
输出[[1]]示例 3输入root []
输出[]提示树中节点数目在范围 [0, 2000] 内
-100 Node.val 100题解
方法一按层模拟BFS
/*** 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 void reverse(ListInteger list){int size list.size();int tmp[] new int[size];for(int i0;isize;i){tmp[i] list.get(i);}int index 0;for(int isize-1;i0;i--){list.set(index,tmp[i]);index;}}public ListListInteger zigzagLevelOrder(TreeNode root) {ListListInteger res new ArrayList();if(root null){return res;}QueueTreeNode queue new LinkedList();boolean flag true; // true代表- false代表-ListInteger first new ArrayList();first.add(root.val);if(root.left ! null)queue.offer(root.left);if(root.right ! null)queue.offer(root.right);res.add(first);while(!queue.isEmpty()){ListInteger tmp new ArrayList();int count queue.size();while(count 0){TreeNode node queue.poll();if(node.left ! null)queue.offer(node.left);if(node.right ! null)queue.offer(node.right);tmp.add(node.val);count--;}flag !flag;if(!flag){//对此时取到的tmp顺序取反reverse(tmp);}res.add(tmp);}return res;}
}方法二双端队列奇偶
/*** 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 ListListInteger zigzagLevelOrder(TreeNode root) {ListListInteger res new ArrayList();if(root null){return res;}QueueTreeNode queue new LinkedList();int len 1;// 奇数代表- 偶数代表-ListInteger first new LinkedList();first.add(root.val);if(root.left ! null)queue.offer(root.left);if(root.right ! null)queue.offer(root.right);res.add(first);len;while(!queue.isEmpty()){// 队列依旧是传统队列但是每一个加入到res中的小list都是用双端形式从而形式上实现双端队列ListInteger tmp new LinkedList();// 也是因为链表形式相较于数组形式更利于反转int count queue.size();while(count 0){TreeNode node queue.poll();if(node.left ! null)queue.add(node.left); if(node.right ! null)queue.offer(node.right);if(len % 2 0){tmp.addFirst(node.val); }else{tmp.addLast(node.val);}count--;}res.add(tmp);len;}return res;}
}
