首页 > 代码库 > Binary Tree Zigzag Level Order Traversal

Binary Tree Zigzag Level Order Traversal

2024-07-18 01:29:28   225人阅读

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]]

思路：每次从后往前对当前层元素进行遍历，这样每层将交替出现顺序、逆序。在保存下一层节点时：如果当前层的元素是顺序的，则应先加入左节点再加入右节点；否则，应先加入右节点再加入左节点。

 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 };

 


联系
我们