102. Binary Tree Level Order Traversal

2017-3-8来源:ASP.NET技巧人气:289

简单树的BFS

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { queue<TreeNode*> level; queue<int> depth; vector<vector<int>> result; if(root==NULL) return result; level.push(root); depth.push(1); while(!level.empty()) { if(level.front()->left!=NULL) { level.push(level.front()->left); depth.push(depth.front()+1); } if(level.front()->right!=NULL) { level.push(level.front()->right); depth.push(depth.front()+1); } if(result.size()<depth.front()) { vector<int> temp; temp.push_back(level.front()->val); result.push_back(temp); } else result[depth.front()-1].push_back(level.front()->val); level.pop(); depth.pop(); } return result; } };