首页 > 代码库 > Binary Tree Zigzag Level Order Traversal
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 7return its zigzag level order traversal as:
[ [3], [20,9], [15,7]]思路：每次从后往前对当前层元素进行遍历，这样每层将交替出现顺序、逆序。在保存下一层节点时：如果当前层的元素是顺序的，则应先加入左节点再加入右节点；否则，应先加入右节点再加入左节点。
1 class Solution { 2 public: 3 vector<vector<int>> zigzagLevelOrder( TreeNode *root ) { 4 vector<vector<int>> zigzags; 5 vector<TreeNode*> nodeList; 6 if( root ) { nodeList.push_back( root ); } 7 while( !nodeList.empty() ) { 8 vector<TreeNode*> newNodeList; 9 vector<int> values;10 for( auto iter = nodeList.rbegin(); iter != nodeList.rend(); ++iter ) {11 values.push_back( (*iter)->val );12 if( (*iter)->left ) { newNodeList.push_back( (*iter)->left ); }13 if( (*iter)->right ) { newNodeList.push_back( (*iter)->right ); }14 }15 zigzags.push_back( values );16 if( newNodeList.empty() ) { break; }17 nodeList.clear(); values.clear();18 for( auto iter = newNodeList.rbegin(); iter != newNodeList.rend(); ++iter ) {19 values.push_back( (*iter)->val );20 if( (*iter)->right ) { nodeList.push_back( (*iter)->right ); }21 if( (*iter)->left ) { nodeList.push_back( (*iter)->left ); }22 }23 zigzags.push_back( values );24 }25 return zigzags;26 }27 };
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。