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

3    / \   9  20     /  \    15   7

return its level order traversal as:

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

confused what 

"{1,#,2,3}" means? 

[Thoughts]

Two ways to resolve this problem:

1. Breadth first search

Initial an int variable to track the node count in each level and print level by level. And here need a QUEUE as a helper.

2. Depth first search

Rely on the recursion. Decrement level by one as you advance to the next level. When level equals 1, you’ve reached the given level and output them.

The cons is, DFS will revisit the node, which make it less efficient than BFS.

[Code]

BFS solution

1:    vector
    
     
       > levelOrder(TreeNode *root) {  2:      // Start typing your C/C++ solution below  3:      // DO NOT write int main() function  4:      vector
      
       
         > result;  5:      vector
        
          sta;  6:      if(root == NULL) return result;  7:      sta.push_back(root);  8:      int nextLevCou=1;  9:      int index=0;  10:      while(index < sta.size())  11:      {  12:        int curLevCou = nextLevCou;  13:        nextLevCou =0;  14:        vector
         
           level; 15: for(int i =index; i< index+curLevCou; i++) 16: { 17: root = sta[i]; 18: level.push_back(root->val); 19: if(root->left!=NULL) 20: { 21: sta.push_back(root->left); 22: nextLevCou++; 23: } 24: if(root->right!=NULL) 25: { 26: sta.push_back(root->right); 27: nextLevCou++; 28: } 29: } 30: result.push_back(level); 31: index = index +curLevCou; 32: } 33: return result; 34: }
         
        
       
      
     
    

DFS solution

1:    vector
    
     
       > levelOrder(TreeNode *root) {  2:      // Start typing your C/C++ solution below  3:      // DO NOT write int main() function      4:      vector
      
       
         > output;  5:      if(!root) return output;  6:      vector
        
          oneLine;  7:      bool hasNextLevel=true;  8:      int currentLevel =1;  9:      while(hasNextLevel)  10:      {  11:        hasNextLevel = false;  12:        LevelTravel(root, currentLevel, hasNextLevel, oneLine);  13:        output.push_back(oneLine);  14:        currentLevel ++;  15:        oneLine.clear();  16:      }  17:      return output;  18:    }  19:    void LevelTravel(  20:      TreeNode* node,   21:      int level,  22:      bool& hasNextLevel,  23:      vector
         
          & result) 24: { 25: if(!node) return; 26: if(level ==1) 27: { 28: result.push_back(node->val); 29: if(node->left || node->right) 30: hasNextLevel = true; 31: return; 32: } 33: else 34: { 35: LevelTravel(node->left, level-1, hasNextLevel, result); 36: LevelTravel(node->right, level-1, hasNextLevel, result); 37: } 38: }
         
        
       
      
     
    

Update 1/12/2014 

BFS的code太啰嗦，用两个循环虽然看着清楚了，但是code不够漂亮，改一下。

1:    vector
    
     
       > levelOrder(TreeNode *root) {  2:      vector
      
       
         > result;  3:      if(root == NULL) return result;  4:      queue
        
          nodeQ;  5:      nodeQ.push(root);  6:      int nextLevelCnt=0, currentLevelCnt=1;  7:      vector
         
           layer; 8: int visitedCnt=0; 9: while(nodeQ.size() != 0) 10: { 11: TreeNode* node = nodeQ.front(); 12: nodeQ.pop(); 13: visitedCnt++; 14: layer.push_back(node->val); 15: if(node->left != NULL) 16: { 17: nodeQ.push(node->left); 18: nextLevelCnt++; 19: } 20: if(node->right != NULL) 21: { 22: nodeQ.push(node->right); 23: nextLevelCnt++; 24: } 25: if(visitedCnt == currentLevelCnt) 26: { 27: visitedCnt =0; 28: currentLevelCnt = nextLevelCnt; 29: nextLevelCnt=0; 30: result.push_back(layer); 31: layer.clear(); 32: } 33: } 34: return result; 35: }