币圈小鱼儿
【BGOEX交易平台在哪里】二叉树的锯齿形层次遍历
摘要：今天来看一道比较简单的题，给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
来源： 数据结构和算法-山大王 wld
问题描述
今天来看一道比较简单的题，给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
例如：
给定二叉树 [3,9,20,null,null,15,7]
3/
9 20
/15 7
返回锯齿形层次遍历如下：
[
[3],
[20,9],
[15,7]
]
BFS 打印
二叉树的的层次遍历就是一层一层的遍历，也就是我们俗称的 BFS （宽度优先搜索算法（又称广度优先搜索））, 树的宽度优先搜索，最简单的方式就是使用队列。但这题打印的时候多了一个条件，就是不能一直从一个方向打印，要先从左边打印然后再从右边打印……，就这样交替进行，所以这里要有个变量来判断是从左往右还是从右往左打印，代码比较简单，我们来看下。
1public List> zigzagLevelOrder(TreeNode root) { 2 List> res = new ArrayList<>(); 3 if (root == null) 4 return res; 5 Queue queue = new LinkedList<>(); 6 queue.add(root); 7 boolean leftToRight = true; 8 while (!queue.isEmpty()) { 9 List level = new ArrayList<>(); 10 // 统计这一行有多少个节点 11 int count = queue.size(); 12 // 遍历这一行的所有节点 13 for (int i = 0; i < count; i++) { 14 //poll 移除队列头部元素（队列在头部移除，尾部添加） 15 TreeNode node = queue.poll(); 16 // 判断是从左往右打印还是从右往左打印。 17 if (leftToRight) { 18 level.add(node.val); 19 } else { 20 level.add(0, node.val); 21 } 22 // 左右子节点如果不为空会被加入到队列中 23 if (node.left != null) 24 queue.add(node.left); 25 if (node.right != null) 26 queue.add(node.right); 27 } 28 res.add(level); 29 leftToRight = !leftToRight; 30 } 31 return res; 32}
上面代码中如果把第 17-21 行的代码直接换成第 18 行的代码就是我们之前讲过的 BFS，就是一层一层往下打印。只不过这里多了一个条件的判断。
当然我们还可以根据每一层是第几层来判断，如果根节点是第 1 层的话，那么我们在层数是奇数的时候从左往右打印，如果层数是偶数的时候从右往左打印。这里我们使用上面两种方式的结合，来看下代码。
1public List> zigzagLevelOrder(TreeNode root) { 2 List> res = new ArrayList<>(); 3 if (root == null) 4 return res; 5 // 双端队列，两边都可以操作 6 Deque deque = new LinkedList<>(); 7 // 添加到队列的头 8 deque.addFirst(root); 9 while (!deque.isEmpty()) { 10 List level = new ArrayList<>(); 11 // 统计这一行有多少个节点 12 int count = deque.size(); 13 // 遍历这一行的所有节点 14 TreeNode cur; 15 for (int i = 0; i < count; i++) { 16 if (res.size() % 2 == 1) { 17 // 从左边往右边打印 18 // 移除队列头部的元素，如果子节点不为空加入到队列的尾部 19 cur = deque.removeFirst(); 20 if (cur.right != null) 21 deque.addLast(cur.right); 22 if (cur.left != null) 23 deque.addLast(cur.left); 24 } else { 25 // 从右边往左边打印 26 // 移除队列尾部的元素，如果子节点不为空加入到队列的头部 27 cur = deque.removeLast(); 28 if (cur.left != null) 29 deque.addFirst(cur.left); 30 if (cur.right != null) 31 deque.addFirst(cur.right); 32 } 33 level.add(cur.val); 34 } 35 res.add(level); 36 } 37 return res; 38}
DFS 打印
这题除了使用 BFS 以外，我们还可以使用 DFS。但这里我们要有个判断，如果走到下一层的时候集合没有创建，我们要先创建下一层的集合，代码也很简单，我们来看下。
1public List<List> zigzagLevelOrder(TreeNode root) { 2 List<List> res = new ArrayList<>(); 3 travel(root, res, 0); 4 return res; 5} 6 7private void travel(TreeNode cur, List<List> res, int level) { 8 if (cur == null) 9 return; 10 // 如果 res.size() <= level 说明下一层的集合还没创建，所以要先创建下一层的集合 11 if (res.size() <= level) { 12 List newLevel = new LinkedList<>(); 13 res.add(newLevel); 14 } 15 // 遍历到第几层我们就操作第几层的数据 16 List list = res.get(level); 17 // 这里默认根节点是第 0 层，偶数层相当于从左往右遍历， 18 // 所以要添加到集合的末尾，如果是奇数层相当于从右往左遍历， 19 // 要把数据添加到集合的开头 20 if (level % 2 == 0) 21 list.add(cur.val); 22 else 23 list.add(0, cur.val); 24 // 分别遍历左右两个子节点，到下一层了，所以层数要加 1 25 travel(cur.left, res, level + 1); 26 travel(cur.right, res, level + 1); 27}
总结
这题最简单的一种方式就是参照二叉树的 BFS 打印，然后稍作修改，如果当前行是从左往右打印，那么下一行就从右往左打印。如果当前行是从右往左打印，那么下一行就从左往右打印，代码基本上没什么难度。
- 免责声明
- 世链财经作为开放的信息发布平台，所有资讯仅代表作者个人观点，与世链财经无关。如文章、图片、音频或视频出现侵权、违规及其他不当言论，请提供相关材料，发送到：2785592653@qq.com。
- 风险提示：本站所提供的资讯不代表任何投资暗示。投资有风险，入市须谨慎。
- 世链粉丝群：提供最新热点新闻，空投糖果、红包等福利，微信：msy2134。
