1.题目
2.思路
层次遍历:借助队列,先将根结点入队,然后循环出队首结点,并且将该结点的左子树和右子树加入队列中。
(1)题目要求输出每层的结点,而常规模板中的队列是各层结点混在一起的,所以为了区分每层,在原本模板的while里面加了个for循环——该for循环即将一层的结点存入layer数组中,之所以for的遍历次数即改层的结点个数width确定,是因为在进入for前的队列长度即为该层的结点个数。
(2)队列中存放的是node*型,而非node型——否则当需要修改队首元素时,就无法对原元素进行修改(只是修改了队列中的副本);当然如果是使用静态二叉链表存树的写法,队列就是queue<int>q了。
(3)由于可能一开始为空树,所以需要判空,即若为空则返回二维数组ans,注意看清返回值,而非返回NULL;
(4)要非常熟练树的模板。
3.代码
/** * 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*>q;//放指针 vector<vector<int>>ans; if(!root) return ans; q.push(root); while(!q.empty()){//如果队列不空 vector<int>layer; layer.clear(); int width=q.size(); for(int i=0;i<width;i++){//把一层的结点存入layer数组中,关键! TreeNode* temp=q.front(); q.pop(); layer.push_back(temp->val); if(temp->left){ q.push(temp->left); } if(temp->right){ q.push(temp->right); } } ans.push_back(layer);//一层完毕 } return ans; } };
在《剑指offer》中的32-I 从上到下打印二叉树,做法和这题是一样的,虽然不需要二维数组,只用一维数组,即不用多个layer
数组:
/** * 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<int> levelOrder(TreeNode* root) { queue<TreeNode*>q; vector<int>ans; if(!root) return ans; q.push(root); while(!q.empty()){ int width = q.size(); for(int i = 0; i < width; i++){ TreeNode* temp = q.front(); q.pop(); ans.push_back(temp->val); if(temp->left){ q.push(temp->left); } if(temp->right){ q.push(temp->right); } } } return ans; } };