题目：请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
例如:
给定二叉树: [3,9,20,null,null,15,7],

  • 3
  • / \
  • 9 20
  • / \
  • 15 7

返回其层次遍历结果：

  • [
  • [3],
  • [20,9],
  • [15,7]
  • ]

提示：

  • 节点总数 <= 1000

    解法1：BFS，广度优先搜索，时间复杂度o(n)，空间复杂度o(n)

  • 创建一个队列，用于存放树，首先加入根节点

  • 两次循环，在循环中，先让当前队头节点出队，然后把判断它的左右子节点是否为空，如果不为空则按左右的顺序加入队列，大循环每次代表一层，小循环代表每个节点

  • 在每一层大循环中，需要判断当前层是否为奇数层，如果是奇数层（从0开始），则需要把临时的list倒置，再加入到结果集res中

    1.           // 翻转list，添加到res
    2.           if(level % 2 == 1){
    3.               Collections.reverse(list);
    4.           }
    5.           res.add(list);
    6.           level++;
    1.   public List<List<Integer>> levelOrder(TreeNode root) {
    2.       if(root == null)
    3.           return new ArrayList<>();
    4.       List<List<Integer>> res = new ArrayList<>();
    5.       Deque<TreeNode> deque = new LinkedList<>();
    6.       deque.offer(root);
    7.       int level = 0;
    8.       while(!deque.isEmpty()){
    9.           int sz = deque.size();
    10.           List<Integer> list = new ArrayList<>();
    11.           for(int i = 0 ; i < sz ; i++){
    12.               TreeNode node = deque.poll();
    13.               list.add(node.val);
    14.               if(node.left != null){
    15.                   deque.offer(node.left);
    16.               }
    17.               if(node.right != null){
    18.                   deque.offer(node.right);
    19.               }
    21.           }
    22.           // 翻转list，添加到res
    23.           if(level % 2 == 1){
    24.               Collections.reverse(list);
    25.           }
    27.           res.add(list);
    28.           level++;
    29.       }
    30.       return res;
    31.   }

  • 改进方式：使用一个布尔变量，少了%运算，因为从第1行开始，每一行都与上一行顺序相反

  • 另外，如果是右往左的添加方式，则list每次把当前元素加在第0个位置即可

    1.   public List<List<Integer>> levelOrder(TreeNode root) {
    2.       if(root == null)
    3.           return new ArrayList<>();
    4.       List<List<Integer>> res = new ArrayList<>();
    5.       Deque<TreeNode> deque = new LinkedList<>();
    6.       deque.offer(root);
    7.       int level = 0;
    8.       boolean leftToRight = true;// 是否从左到右
    9.       while(!deque.isEmpty()){
    10.           int sz = deque.size();
    11.           List<Integer> list = new ArrayList<>();
    12.           for(int i = 0 ; i < sz ; i++){
    13.               TreeNode node = deque.poll();
    14.               // 如果是正序
    15.               if(leftToRight){
    16.                   list.add(node.val);
    17.               }else{
    18.                   list.add(0,node.val);
    19.               }
    21.               if(node.left != null){
    22.                   deque.offer(node.left);
    23.               }
    24.               if(node.right != null){
    25.                   deque.offer(node.right);
    26.               }           
    27.           }
    29.           res.add(list);
    30.           leftToRight = !leftToRight;
    31.       }
    32.       return res;
    33.   }

    解法2：奇偶分层打印，时间复杂度o(n)，空间复杂度o(n)

  1. 依然按照每层顺序打印
  2. 奇数层：各个节点顺序加入list尾部
  3. 偶数层：各个节点依次加入list前面 ```java class Solution { LinkedList> res = new LinkedList<>(); public List> levelOrder(TreeNode root) {
    1.  if(root == null)
    2.      return res;
    3.  Deque<TreeNode> deque = new LinkedList<>();
    4.  deque.add(root);
    5.  boolean odd_level = true;
    6.  while(!deque.isEmpty()){
    7.      int sz = deque.size();
    8.      LinkedList<Integer> list = new LinkedList<>();
    9.      for(int i = 0 ; i < sz ; i++){
    10.          TreeNode node = deque.poll();
    11.          if(odd_level == true)
    12.              list.addLast(node.val);
    13.          else 
    14.              list.addFirst(node.val);
    15.          if(node.left != null)
    16.              deque.add(node.left);
    17.          if(node.right != null)
    18.              deque.add(node.right);
    19.      }
    20.      odd_level = !odd_level;
    21.      res.addLast(list);
    22.  }
    23.  return res;
    }

}

<a name="pr2YS"></a>
## 解法3：DFS，深度优先搜索，时间复杂度O(n)，空间复杂度O(n)

1. 递归的结束条件为,root == null返回
1. 递归时，需要考虑到层级和当前list的大小，如果当前层级 >= List的大小，说明已经到了下一层，需要重新new 一个list
```java
        // 说明需要到下一层了    
        if(level >= res.size()){
            res.add(new ArrayList());
        }

  1. 先在对应层级添加对应元素，然后进行递归调用，需要先左再右，level层级+1，递归调用时，需要根据当前的level，如果level是奇数，则添加顺序为从左到右，否则为从右到左（每次把当前元素添加到最前面）

         if((level & 1) == 0)
         res.get(level).add(root.val);
     else 
         res.get(level).add(0,node.val);
     dfs(res,root.left,level+1);
     dfs(res,root.right,level+1);

     public List<List<Integer>> levelOrder(TreeNode root) {
     if(root == null)
         return new ArrayList<>();
     List<List<Integer>> res = new ArrayList<>();
     dfs(res,root,0);
     return res;
 }

 public void dfs(List<List<Integer>> res,TreeNode root,Integer level){
     if(root == null)
         return;
     if(level >= res.size()){
         res.add(new ArrayList());
     }
     if((level & 1) == 0)
         res.get(level).add(root.val);
     else 
         res.get(level).add(0,node.val);
     dfs(res,root.left,level+1);
     dfs(res,root.right,level+1);
 }