剑指offer 59. 按之字形顺序打印二叉树

59. 按之字形顺序打印二叉树

题目描述

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

思路：

层序遍历，如果flag 为true ,则表示 从左至右打印，否则从右至左打印

 1 import java.util.Queue;
 2 import java.util.LinkedList;
 3 public class Solution {
 4     public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
 5         // 层序遍历，如果flag 为true ,则表示 从左至右打印，否则从右至左打印
 6         ArrayList<ArrayList<Integer>> list = new ArrayList<>();
 7         if(pRoot == null)
 8             return list;            
 9         Queue<TreeNode> queue = new LinkedList<TreeNode>();
10         queue.offer(pRoot);
11         TreeNode top;
12         int count = 1;        // 当前层的结点数
13         boolean flag = true;
14         ArrayList<Integer> innerList = new ArrayList<>();
15         // 每当上一层的结点完全出队后就重置 flag
16         while(!queue.isEmpty()){
17             count--;
18             top = queue.poll();
19             // 从左至右打印则插入到list的尾部
20             if(flag)
21                 innerList.add(top.val);
22             else      // 从右至左打印则将当前访问的结点插入到 list 的头部
23                 innerList.add(0, top.val);
24            if(top.left != null)
25                queue.offer(top.left);
26             if(top.right != null)
27                 queue.offer(top.right);
28             if(count == 0){        // 开始新的一层
29                 count = queue.size();
30                 flag = !flag;
31                 list.add(innerList);
32                 innerList = new ArrayList<Integer>();
33             }
34         }
35         return list;
36     }
37 
38 }

存储内部 ArrayList 的另一种思路

 1 public class Solution {
 2     public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
 3         // 层序遍历，每次访问一层的元素，并且入队下一层的元素
 4         ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
 5         if(pRoot == null){
 6             return list;
 7         }
 8         // 如果 flag 为 1, 存入 innnerList 的头部，否则存入尾部
 9         Queue<TreeNode> queue = new LinkedList<TreeNode>();
10         queue.offer(pRoot);
11         int flag = 0;            // 存入尾部
12         TreeNode top;
13         while(!queue.isEmpty()){
14             int count = queue.size();
15             // 创建 List
16             ArrayList<Integer> innerList = new ArrayList<Integer>();
17             for(int i = 0; i < count; i++){
18                                 
19                  // 出队元素
20                 top = queue.poll();
21                 // 将元素放入 List
22                 if(flag == 0){
23                     innerList.add(top.val);
24                 }else{
25                     innerList.add(0, top.val);
26                 }
27                 // 入队子类
28                 if(top.left != null)
29                     queue.offer(top.left);
30                 if(top.right != null)
31                     queue.offer(top.right);
32             }
33             // 将innerList 存入 list
34             list.add(innerList);
35             flag = flag == 0 ? 1 : 0;
36         }
37         return list;
38     }
39 
40 }

最后还可以使用LinkedList代替 ArrayList 来提高存储效率，因为这里把元素存入列表刚好更符合LinkedList的高效操作

 1 class Solution {
 2     public List<List<Integer>> levelOrder(TreeNode root) {
 3         // 层序遍历，如果标志位为true,把结点插入到临时列表尾部，否则插入到临时列表头部
 4         List<List<Integer>> res = new ArrayList<>();
 5         if(root == null){
 6             return res;
 7         }
 8         Queue<TreeNode> queue = new LinkedList<>();
 9         queue.offer(root);
10         boolean flag = true;
11         int count = 0;
12         TreeNode top = null;
13         LinkedList<Integer> temp = null;
14         while(!queue.isEmpty()){
15             count = queue.size();
16             temp = new LinkedList<Integer>();
17             for(int i = 0; i < count; i++){
18                 top = queue.poll();
19                 if(flag){
20                     temp.addLast(top.val);
21                 }else{
22                     temp.addFirst(top.val);
23                 }
24 
25                 // 把左右子树入队
26                 if(top.left != null){
27                     queue.offer(top.left);
28                 }
29                 if(top.right != null){
30                     queue.offer(top.right);
31                 }
32             }
33             flag = !flag;   // 标志位取反
34             res.add(temp);
35         }
36         return res;
37     }
38 }

leetcode运行时间为1ms, 空间为38.8MB

复杂度分析：

时间复杂度：对所有结点都访问了一次，所以时间复杂度为O(n)

空间复杂度：每个结点都需要被存储一遍，所以空间复杂度为O(n)