利用队列层次遍历
思路:
假如不需要把各层的元素都放入到同一个数组中的话只需要利用一个队列,先把根节点放入到队列中,再将根节点的左右节点放入到队列中即可。现在要求将同一层的元素放入同一个列表只需要给定一个ind来记录当前放入到数组的元素的个数,当Ind达到进入循环前的队列长度时即可将数组放入最终结果中。
代码
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ class Solution { public: /** * * @param root TreeNode类 * @return int整型vector<vector<>> */ vector<vector<int>> res; vector<int> temp; vector<vector<int> > levelOrder(TreeNode* root) { if(!root) { return {}; } queue<TreeNode*> q; q.push(root); while(!q.empty()) { int length = q.size(); int ind = 0; while(ind<length) { root = q.front(); q.pop(); if(root->left) { q.push(root->left); } if(root->right) { q.push(root->right); } temp.push_back(root->val); ind++; } res.push_back(temp); temp.clear(); } return res; } };