二叉树|二叉树层序遍历和深化算法|数据结构

算法设计中的二叉树层序遍历题目1：给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历）
例如：
给定的二叉树是{3,9,20,#,#,15,7},
3? / ? 9 20? / ? 15 7
该二叉树层序遍历的结果是
[? [3],? [9,20],? [15,7]?]
解题思路：首先利用一个队列来存放每一层的树节点，再取出逐一取出队列中同一层的树节点，再将该树节点的左右节点存放到队列中，直到队列为空。`

public ArrayList> levelOrder(TreeNode root) { ArrayList> lists=new ArrayList<>(); //用于存放所以结果的链表 LinkedBlockingQueue queue=new LinkedBlockingQueue<>(); if (root!=null)//如果头节点不为空的话将头结点存入队列中 queue.offer(root); while (!queue.isEmpty()){ ArrayList list=new ArrayList<>(); TreeNode poll; int size=queue.size(); //记录每一层的树节点数量，方便取出同一层的节点。 for (int i = 0; i < size; i++) {//遍历队列 poll = queue.poll(); list.add(poll.val); if (poll.left != null) queue.offer(poll.left); if (poll.right != null) queue.offer(poll.right); } lists.add(list); } return lists; }

深化练习题目2：给定一个二叉树，返回该二叉树的之字形层序遍历，（从左向右，下一层从右向左，一直这样交替）
例如：
给定的二叉树是{3,9,20,#,#,15,7},
3? / ? 9 20? / ? 15 7
该二叉树之字形层序遍历的结果是
[? [3],? [20,9],? [15,7]?]
【二叉树|二叉树层序遍历和深化】解题思路：在题目一的基础上添加一个方向标志即可。

public ArrayList> zigzagLevelOrder(TreeNode root) { ArrayList> lists=new ArrayList<>(); LinkedBlockingQueue queue=new LinkedBlockingQueue<>(); if (root!=null) queue.offer(root); int p=1; //方向标志 while (!queue.isEmpty()){ ArrayList list=new ArrayList<>(); TreeNode poll; int size=queue.size(); for (int i = 0; i < size; i++) { poll = queue.poll(); list.add(poll.val); if (poll.left != null) queue.offer(poll.left); if (poll.right != null) queue.offer(poll.right); } if (p%2==0){//如果为偶数的话方向为右到左（标志也可以设置为布尔类型true或false） ArrayList list1=new ArrayList<>(); for (int i = list.size()-1; i >=0; i--) { list1.add(list.get(i)); } lists.add(list1); }else lists.add(list); p++; } return lists; }