【题解】【BT】【Leetcode】Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

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

return its level order traversal as:

[

  [3],

  [9,20],

  [15,7]

]

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

思路：

重点在于每层元素个数不定，如何标记一层的结束，往堆栈里push很多NULL来表示空位这种方案，会造成Memory Limit Exceeded。

可以采取记下每层的NULL数量，下层翻倍这种方式计数，满额push标记NULL作为一层的结束

代码：

 vector<vector<int> > levelOrder(TreeNode *root) {

     vector<vector<int> > orders;

     if(root == NULL)

         return orders;

     vector<int> vtmp;

     queue<TreeNode*> tque;

     tque.push(root);

     tque.push(NULL);

     int size = ;

     int count = ;

     int zero = ;//该层的NULL数

     while(!tque.empty()){

         TreeNode * tmp = tque.front();//$$$$

         tque.pop();//void pop()

         if(tmp == NULL){//NULL标识一层的结束

             if(!vtmp.empty())//最后一行可能不满

                 orders.push_back(vtmp);

             vtmp.clear();

             continue;

         }

         vtmp.push_back(tmp->val);

         if(tmp->left != NULL){

             tque.push(tmp->left);

             count++;

         }

         else

             zero++;

         if(tmp->right != NULL){

             tque.push(tmp->right);

             count++;

         }

         else

             zero++;

         if(count + zero == size){

             tque.push(NULL);

             count = ;

             size *= ;

             zero = zero * ;

         }

     }

     return orders;

 }

巴特西

【题解】【BT】【Leetcode】Binary Tree Level Order Traversal

最新文章

热门文章