#include<cstdio> #include<cstdlib> #include<cmath> #include<ctime> #include<cstring> #include<cassert> #include<climits> #include<iostream> #include<sstream> #include<vector> #include<set> #include<map> #include<stack> #include<queue> #include<bitset> #include<algorithm> #include<iterator> #include<string> #include<tuple> #include<random> #include <chrono> using namespace std; struct TreeNode {     int val;     TreeNode* left;     TreeNode* right;     TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; void zigzag(TreeNode* root) {     vector<TreeNode*> pts;     if (NULL == root)         return;     queue<TreeNode*> q;     q.push(root);     int num1 = 1, num2 = 0;     TreeNode* cur = NULL;     while (!q.empty()) {         cur = q.front();         q.pop();         if (cur->left != NULL) {             q.push(cur->left);             num2++;         }         if (cur->right != NULL) {             q.push(cur->right);             num2++;         }         pts.push_back(cur);         num1--;         if (0 == num1) {             pts.push_back(NULL);             num1 = num2;             num2 = 0;         }     }     int n = pts.size();     int rev = 0;     int i, j;     i = -1;     int mid, sum;     while (i < n) {         j = i + 1;         while (j < n && pts[j] != NULL)             j++;         // reverse         if (rev) {             mid = i + (j - i) / 2;             sum = i + j;             for (int x=i+1; x<=mid; x++)                 swap(pts[x], pts[sum-x]);         }         rev = !rev;         i = j;     }     for (i=0; i<n; i++)         if (pts[i] != NULL)             printf(" %d ", pts[i]->val); } int main() {     TreeNode* root = new TreeNode(1);     root->left = new TreeNode(2);     root->right = new TreeNode(3);     root->left->left = new TreeNode(4);     root->right->left = new TreeNode(5);     root->right->right = new TreeNode(6);     zigzag(root);     return 0; } 用普通的队列加标记即可实现。