白云区网站开发公司,工程公司名字大全,开发公司与物业公司的交接手续,国际新闻最新消息今天简短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;}
}
