leetcode-103 Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example: Given binary tree [3,9,20,null,null,15,7],

3 / \ 9 20 / \ 15 7

 

return its zigzag level order traversal as:

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

 

将节点左到右的顺序，然后再是节点右到左的顺序进行遍历：

运用上一题目中的方法二：

具体实现如下，通过list的一个存储

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {              List<List<Integer>> res = new ArrayList<>();         if(root == null) return res;          List<TreeNode> nodes = new ArrayList<>();         nodes.add(root);         boolean leftToRight = false;         while (nodes != null && !nodes.isEmpty()) {             List<Integer> tmpRes = new ArrayList<>();             List<TreeNode> tmpNodes = new ArrayList<>();

            while (nodes != null && !nodes.isEmpty()) {                 TreeNode now = nodes.get(nodes.size()-1);                 tmpRes.add(now.val);                 if (leftToRight) {                     if(now.right!=null) tmpNodes.add(now.right);                      if(now.left!=null) tmpNodes.add(now.left);                                       } else {                     if(now.left!=null) tmpNodes.add(now.left);                      if(now.right!=null) tmpNodes.add(now.right);                                      }                 nodes.remove(nodes.size()-1);             }             if (leftToRight) {                 leftToRight = false;             }else {                 leftToRight = true;             }             res.add(tmpRes);             nodes = tmpNodes;         }         return res;     }