Binary Tree Zigzag Level Order Traversal-白红宇

Binary Tree Zigzag Level Order Traversal

阅读量：4070 次

发布时间：2019-05-25

本文共 968 字，大约阅读时间需要 3 分钟。

题目解析：这个问题的实质是要我们按成访问二叉树的结点，并返回每层访问的结果，这里要求走Z字，其实就是一行正向一行反向。

/*  the kernel idea is visit a binary search tree in level and   the additional work we have to label the end of one level.*/vector
   
    
      > zigzagLevelOrder(TreeNode *root) {	vector
     
      
        > re;	if(root == NULL)		return re;	queue
       
         visit;	vector
        
          level; visit.push(root); //NULL stands for the end of this level visit.push(NULL); //in store every level result, we are asked to change direction. bool reback = false; while (!visit.empty()) { TreeNode* cur = visit.front(); visit.pop(); if(cur != NULL){ if(cur->left) visit.push(cur->left); if(cur->right) visit.push(cur->right); level.push_back(cur->val); } else { if(reback) { vector
         
           rlevel(level.rbegin(),level.rend()); re.push_back(rlevel); } else re.push_back(level); //remember to clear this level. level.clear(); reback = !reback; if(!visit.empty()) visit.push(NULL); } } return re;}