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

3   / \  9  20    /  \   15   7

 

return its level order traversal as:

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

 

解法一：递归

参考了Discussion中stellari的做法，递归进行层次遍历，并将每个level对应于相应的vector。

/** * Definition for binary tree * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution{public:    vector
     
      
        > result;    void levelTra(TreeNode *root, int level)    {        if(root == NULL)            return;        if(level == result.size())        {            vector
       
         v;            result.push_back(v);        }        result[level].push_back(root->val);        levelTra(root->left, level+1);        levelTra(root->right, level+1);    }    vector
        
         
           > levelOrder(TreeNode *root)     {        levelTra(root, 0);        return result;    }};
         
        
       
      
     

 

解法二：

层次遍历，层数使用level来记录。同层装入同一个vector。

当进入新的一层时，将上层的vector保存，并清空。

/** * Definition for binary tree * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ struct Node{    TreeNode* tNode;    int level;    Node(TreeNode* newtNode, int newlevel): tNode(newtNode), level(newlevel) {}};class Solution {public:    vector
     
      
        > levelOrder(TreeNode *root) {        vector
       
        
          > ret;        if(!root)            return ret;        // push root         Node* rootNode = new Node(root, 0);        queue
         
           Nqueue;        Nqueue.push(rootNode);                vector
          
            cur; int curlevel = 0; while(!Nqueue.empty()) { Node* frontNode = Nqueue.front(); Nqueue.pop(); if(frontNode->level > curlevel) { ret.push_back(cur); cur.clear(); curlevel = frontNode->level; } cur.push_back(frontNode->tNode->val); if(frontNode->tNode->left) { Node* leftNode = new Node(frontNode->tNode->left, frontNode->level+1); Nqueue.push(leftNode); } if(frontNode->tNode->right) { Node* rightNode = new Node(frontNode->tNode->right, frontNode->level+1); Nqueue.push(rightNode); } } ret.push_back(cur); return ret; }};