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

Binary Tree Level Order Traversal II

2024-07-18 00:51:56   215人阅读

Given a binary tree, return the bottom-up level order traversal of its nodes‘ values. (ie, from left to right, level by level from leaf to root).

For example:

Given binary tree {3,9,20,#,#,15,7},

    3   /   9  20    /     15   7

return its bottom-up level order traversal as:

[  [15,7],  [9,20],  [3]]

思路：对输入二叉树进行广度优先遍历。得到root-to-leaf次序的每一层的数据，其逆序即为leaf-to-root的结果。

 1 class Solution { 2 public: 3     vector<vector<int>> levelOrderBottom( TreeNode *root ) { 4         vector<vector<int>> levels; 5         if( !root ) { return levels; } 6         vector<TreeNode*> nodes( 1, root ); 7         while( !nodes.empty() ) { 8             vector<TreeNode*> new_nodes; 9             vector<int> values;10             for( auto iter = nodes.begin(); iter != nodes.end(); ++iter ) {11                 values.push_back( (*iter)->val );12                 if( (*iter)->left ) { new_nodes.push_back( (*iter)->left ); }13                 if( (*iter)->right ) { new_nodes.push_back( (*iter)->right ); }14             }15             nodes = new_nodes;16             levels.push_back( values );17         }18         vector<vector<int>> results;19         for( size_t i = levels.size(); i != 0; --i ) {20             results.push_back( levels[i-1] );21         }22         return results;23     }24 };

 


联系
我们