leetcode103. 二叉树的锯齿形层次遍历

给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

例如：
给定二叉树 [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
返回锯齿形层次遍历如下：

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

思路：达到层次遍历的效果后，把奇数下标的list反转一下即可。

或者双端队列，奇数层放的时候放开头，偶数层放结尾。

      /**
       * Definition for a binary tree node.
       * public class TreeNode {
       * int val;
       * TreeNode left;
       * TreeNode right;
       * TreeNode(int x) { val = x; }
       * }
       */
      class Solution {
       List<List<Integer>> levels = new ArrayList<List<Integer>>();
      public void helper(TreeNode node, int level) {
      if (levels.size() == level)levels.add(new ArrayList<Integer>());
       levels.get(level).add(node.val);
      if (node.left != null)
       helper(node.left, level + 1);
      if (node.right != null)
       helper(node.right, level + 1);
       }
      public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
      if (root == null) return levels;
       helper(root, 0);
      for(int i=1;i<levels.size();i+=2)Collections.reverse(levels.get(i));
      return levels;
       }
      }
  
 

文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。

原文链接：fantianzuo.blog.csdn.net/article/details/104370905