之字形层次遍历二叉树-白红宇

之字形层次遍历二叉树：层次遍历二叉树，并且奇数行为从左到右（根节点为第一层），偶数行为从右到左。先写一个容易实现的，参照《编程之美》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; }};