Binary Tree Zigzag Level Order Traversal
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] ]
思路:
通过迭代方法按行访问。然后每访问一行,改变一次访问顺序和存放子结点的顺序。
题解:
/** * 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<vector<int> > zigzagLevelOrder(TreeNode *root) { vector<vector<int>> ret; if (root == nullptr) return ret; // direction of visiting bool fwd_direction = false; list<TreeNode*> this_row; list<TreeNode*> next_row; this_row.push_back(root); ret.push_back(vector<int>()); while(!this_row.empty()) { TreeNode* l; if (fwd_direction) { l = this_row.front(); this_row.pop_front(); } else { l = this_row.back(); this_row.pop_back(); } ret.back().push_back(l->val); if (fwd_direction) { if (l->right != nullptr) next_row.push_back(l->right); if (l->left != nullptr) next_row.push_back(l->left); } else { if (l->left != nullptr) next_row.push_front(l->left); if (l->right != nullptr) next_row.push_front(l->right); } if (this_row.empty()) { swap(this_row, next_row); ret.push_back(vector<int>()); fwd_direction = !fwd_direction; } } //if (ret.back().empty()) ret.pop_back(); return ret; } };