之字形层次遍历二叉树：层次遍历二叉树，并且奇数行为从左到右（根节点为第一层），偶数行为从右到左。

先写一个容易实现的，参照《编程之美》3.10分层遍历二叉树的做法，先编写一个用来处理制定层的函数，然后逐层调用这个函数即可。

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,#,#,15,7},

3

/ 9 20

/ 15 7

return its zigzag level order traversal as:

[

[3],

[20,9],

[15,7]]

confused what"{1,#,2,3}"means? > read more on how binary tree is serialized on OJ.

OJ's Binary Tree Serialization:

The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.

Here's an example:

1

/ 2 3

/

4

5

The above binary tree is serialized as"{1,2,3,#,#,4,#,#,5}".

/** * Definition for binary tree * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public:    vector
    
     
       > zigzagLevelOrder(TreeNode* root){        vector
      
       
         >result;        for (int level = 0;; level++){            vector
        
          q = ZigzagNodeAtLevel(root, level);            if (q.size() == 0){                break;            }            result.push_back(q);        }        return result;    }    vector
         
           ZigzagNodeAtLevel(TreeNode* root, int level){ vector
          
            res; if (!root || level<0){ return res; } if (level == 0){ res.push_back(root->val); } // return PrintNodeAtLevel(root->left, level - 1) + PrintNodeAtLevel(root->right, level - 1); vector
           
             left_res = ZigzagNodeAtLevel(root->left, level - 1); vector
            
              right_res = ZigzagNodeAtLevel(root->right, level - 1); if(level%2==1){ for (int i = right_res.size()-1; i>=0; i--){ res.push_back(right_res[i]); } for (int i = left_res.size()-1; i >=0; i--){ res.push_back(left_res[i]); } }else{ for (int i = left_res.size()-1; i >=0; i--){ res.push_back(left_res[i]); } for (int i = right_res.size()-1; i>=0; i--){ res.push_back(right_res[i]); } } return res; }};