题解 | #按之字形顺序打印二叉树#
按之字形顺序打印二叉树
https://www.nowcoder.com/practice/91b69814117f4e8097390d107d2efbe0
双端队列
/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } }; */ class Solution { public: vector<vector<int> > Print(TreeNode* pRoot) { vector<vector<int>> ret; if (pRoot == nullptr) { return ret; } deque<TreeNode*> treeDeque; treeDeque.push_back(pRoot); int direction = 1; while (!treeDeque.empty()) { int num = treeDeque.size(); vector<int> lineData; for (int i = 0; i < num; ++i) { if (direction) { TreeNode* temNode = treeDeque.front(); treeDeque.pop_front(); if(temNode->left) { treeDeque.push_back(temNode->left); } if(temNode->right) { treeDeque.push_back(temNode->right); } lineData.push_back(temNode->val); } else { TreeNode* temNode=treeDeque.back(); treeDeque.pop_back(); if(temNode->right) { treeDeque.push_front(temNode->right); } if(temNode->left) { treeDeque.push_front(temNode->left); } lineData.push_back(temNode->val); } } ret.emplace_back(lineData); direction=direction==1?0:1; } return ret; } };