[LeetCode]Binary Tree Level Order Traversal-白红宇

[LeetCode]Binary Tree Level Order Traversal

阅读量：4150 次

发布时间：2019-05-25

本文共 2510 字，大约阅读时间需要 8 分钟。

struct TreeNode {	int val;	TreeNode *left;	TreeNode *right;	TreeNode(int x) : val(x), left(NULL), right(NULL) {}};class Solution {	//BFS is always work for the level order traverse of a tree	//all we need is add some additional information, to solve the specific problem of level order typepublic:	vector
   
    
     > LevelOrder_BFS(TreeNode* root)	{		vector
     
      
       > ans;		if(!root)//put the null tree judge here will be more neet			return ans;		queue
       
        
         > q; int stepNow = 0; q.push(make_pair(root, stepNow)); vector
         
           curLevel; while(!q.empty()) { TreeNode* curNode = q.front().first; int curStep = q.front().second; q.pop(); if(curStep != stepNow) { ans.push_back(curLevel); curLevel.clear(); stepNow = curStep; } curLevel.push_back(curNode->val); if(curNode->left) q.push(make_pair(curNode->left, curStep+1)); if(curNode->right) q.push(make_pair(curNode->right, curStep+1)); } ans.push_back(curLevel);//note: we should remember the last level here return ans; } vector
          
           
             > levelOrder(TreeNode *root) { // Start typing your C/C++ solution below // DO NOT write int main() function return LevelOrder_BFS(root); }};

second time

/** * Definition for binary tree * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public:    struct Node    {        TreeNode* treeNode;        int level;        Node(TreeNode* _treeNode = NULL, int _level = 0):treeNode(_treeNode), level(_level){};    };    vector
   
    
      > levelOrder(TreeNode *root) {        // Start typing your C/C++ solution below        // DO NOT write int main() function        if(root == NULL) return vector
     
      
        >();        queue
       
         nodeQ;        nodeQ.push(Node(root, 1));        int prevLevel = 0;        vector
        
          curLevelAns; vector
         
          
            > allLevelAns; while(!nodeQ.empty()) { TreeNode* curNode = nodeQ.front().treeNode; int curLevel = nodeQ.front().level; nodeQ.pop(); if(curNode == NULL) continue; if(curLevel != prevLevel) { if(prevLevel != 0) allLevelAns.push_back(curLevelAns); curLevelAns.clear(); } prevLevel = curLevel; curLevelAns.push_back(curNode->val); nodeQ.push(Node(curNode->left, curLevel+1)); nodeQ.push(Node(curNode->right, curLevel+1)); } allLevelAns.push_back(curLevelAns); return allLevelAns; }};