c++ implementation — zigzag printing binary tree

Hits: 0

[Question: Please implement a function to print a binary tree] in a zigzag pattern , that is, the first line is printed in left-to-right order, the second layer is printed in right-to-left order, the third line is printed in left-to-right order, and the other line and so on.
It is very similar to the previous printing binary tree, so it is solved in the same way. It is very convenient to use bfs to solve it with the help of [queues .]
First review the template:
if you don’t need to determine which level you are currently traversing, the template is as follows:

void bfs() {
 vis[] = {0}; // or set
 queue<int> pq(start_val);

 while (!pq.empty()) {
      int cur = pq.front(); pq.pop();
      for (traverse all adjacent nodes nex of cur) {
          if (nex node is valid && vis[nex]== 0 ){
             vis[nex] = 1;
             pq.push(nex)
         }
     } // end for
 } // end while
}

If you need to determine which layer to traverse, the template is as follows:

void bfs() {
 int level = 0;
 vis[] = {0}; // or set
 queue<int> pq(original_val);
 while (!pq.empty()) {
     int sz = pq.size();

     while (sz--) {
              int cur = pq.front(); pq.pop();
          for (traverse all adjacent nodes nex of cur) {
              if (nex node is valid && vis[nex] == 0 ) {
                 vis[nex] = 1;
                 pq.push(nex)
             }
         } // end for
     } // end inner while
     level++;

 } // end outer while
}

The key idea of ​​this question is to traverse the odd-numbered layers from left to right, and the even-numbered layers from right to left; the
code is as follows:

class Solution {
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
        vector<vector<int>> res;
        if(!pRoot){
            return res;
        }
        queue<TreeNode*> help;
        help.push(pRoot);
        int level=0;
        while(!help.empty()){
            int sz=help.size();
            vector<int> ans;
            while(sz--){
                 TreeNode *node=help.front();
                 help.pop();
                ans.push_back(node->val);
                if(node->left) help.push(node->left);
                if(node->right) help.push(node->right);
            }
            ++level;
            if (!(level& 1 )){ //Use bit operations to quickly determine whether a number is even or odd 
                reverse(ans.begin(), ans.end()); //If it is an even level, reverse the vector
            }
            res.push_back(ans);
        }
        return res;
    }

};

You may also like...

Leave a Reply

Your email address will not be published.