LeetCode 树 103. 二叉树的锯齿形层次遍历（双端队列 DFS的空间复杂度）

这道题目乍一看很简单，而且也做出来了，但其实反应出了剑指offer中提出的两个问题

第一个便是处理小错误和特殊输入的能力，这道题做的过程中出了很多小错误

第二个是找寻更好算法的能力，这道题有更好的算法。

首先说原本自己写的算法：
一开始看到这种锯齿形算法，当然想到的是层序遍历，然后要改变队列先进先出的特性，弄一种能满足题目需要的数据结构（其实就是后面解法的双端队列）。

但是后来又一想，那不如直接在层序遍历的基础上加一个flag，分奇数偶数层，然后偶数层翻转一下LIst不就行了。

以下是代码：

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        Queue<TreeNode> queue=new ArrayDeque<>();
        List<List<Integer>> listReturn=new ArrayList<>();
        if(root==null)
        {return new ArrayList<>();}
        queue.add(root);
        int flag=0;
        while(queue.size()!=0)
        {
            int count=queue.size();
            List<Integer> list=new ArrayList<>();
            for(int i=0;i<count;i++)
            {
                TreeNode node= queue.poll();
                if(node.left!=null)
                {queue.add(node.left);}
                if(node.right!=null)
                {queue.add(node.right);}
                list.add(node.val);
            }
            if(flag==1)
            {
                Collections.reverse(list);
                listReturn.add(list);
                flag=0;
            }
            else
            {
                listReturn.add(list);
                flag=1;
            }
        }
        return listReturn;
    }
}

写的时候出了几个问题：

如果树为空，返回什么。之前做了几个类似的题目，知道需要做这个特殊情况的判断，于是也写的是返回null。但这里的要返回的是分层的列表而不是根节点，所以应该直接返回一个空列表。
if(node.left!=null)这个条件开始忘写了，也是够了。。。
当天写代码的之前写了一些Python的代码，这边一开始list的add都写成了append。看来基本的方法还是要记清楚。

另外一种算法就很容易想到了，双端队列的方式，直接在数据结构层面就把功能实现了

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
  public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    if (root == null) {
      return new ArrayList<List<Integer>>();
    }

    List<List<Integer>> results = new ArrayList<List<Integer>>();

    // add the root element with a delimiter to kick off the BFS loop
    Deque<TreeNode> node_queue = new LinkedList<TreeNode>();
    node_queue.addLast(root);
    node_queue.addLast(null);

    LinkedList<Integer> level_list = new LinkedList<Integer>();
    boolean is_order_left = true;

    while (node_queue.size() > 0) {
      TreeNode curr_node = node_queue.pollFirst();
      if (curr_node != null) {
        if (is_order_left)
          level_list.addLast(curr_node.val);
        else
          level_list.addFirst(curr_node.val);

        if (curr_node.left != null)
          node_queue.addLast(curr_node.left);
        if (curr_node.right != null)
          node_queue.addLast(curr_node.right);

      } else {
        // we finish the scan of one level
        results.add(level_list);
        level_list = new LinkedList<Integer>();
        // prepare for the next level
        if (node_queue.size() > 0)
          node_queue.addLast(null);
        is_order_left = !is_order_left;
      }
    }
    return results;
  }
}

这里是LeetCode的官方解法，用的是null分层，其实不如直接计数来的明白。

更偏好这种解法的原因是，每次翻转列表肯定要消耗一定时间，但算法的时间复杂度会不会提升呢？在LeetCode判题中没有提升。。。

再下一种就是深度优先搜索的办法

这种算法的逻辑就是，建立一个索引和层数挂钩的List

然后在DFS中，不需要按照逐层遍历嘛，反正把对应层的节点加入对应level的List节点就行了，当然要根据level的奇数偶数决定顺序插还是反序插。然后他的每一个节点还是用Deque Linkedlist实现的。

优点在于空间复杂度

之前层序遍历的空间复杂度是：

DFS的优点等于是，调用堆栈的空间复杂度是logN级别的，调用队列是ON级别的？

递归调用栈的深度 = 所占空间 = O(H)

所以这样看DFS在空间复杂度上还是有天然优势啊。。。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
  protected void DFS(TreeNode node, int level, List<List<Integer>> results) {
    if (level >= results.size()) {
      LinkedList<Integer> newLevel = new LinkedList<Integer>();
      newLevel.add(node.val);
      results.add(newLevel);
    } else {
      if (level % 2 == 0)
        results.get(level).add(node.val);
      else
        results.get(level).add(0, node.val);
    }

    if (node.left != null) DFS(node.left, level + 1, results);
    if (node.right != null) DFS(node.right, level + 1, results);
  }

  public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    if (root == null) {
      return new ArrayList<List<Integer>>();
    }
    List<List<Integer>> results = new ArrayList<List<Integer>>();
    DFS(root, 0, results);
    return results;
  }
}